LeetCode-8

581. 最短无序连续子数组

思路

1. 拷贝把备份排序，然后两个指针，依次从头到尾（i），从尾到头（j）比较排序前后两个数组相同下标的值，把第一次不同的下标值记录，最后返回j - i + 1，如果为负数返回0。

AC代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> cpy(nums.begin(), nums.end());
        sort(cpy.begin(), cpy.end());
        int len = nums.size();
        int j = len - 1, i = 0;
        for ( ; j >= 0; j--) {
            if (nums[j] != cpy[j]) {
                break;
            }
        }
        for (; i < len; i++) {
            if (nums[i] != cpy[i]) {
                break;
            }
        }
        int ans = j - i + 1;
        return ans > 0 ? ans : 0;
    }
};

思路