[每日 LeetCode] 581. Shortest Unsorted Continuous Subarray

Description:

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
​

Note:

1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means <=.

思路：考虑最容易理解的方式，缺点是空间复杂度为 O(n)。使用一个辅助数组，新数组复制原数组的值，然后对新数组排序。从数组起始位置开始，两个数组相互比较，当对应位置数字不同的时候停止，同理再从末尾开始，对应位置上比较，也是遇到不同的数字时停止，这样中间一段就是最短无序连续子数组。

C++ 代码

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int i = 0;
        int j = n - 1;
        vector<int> temp = nums;
        sort(temp.begin(),temp.end());
        while(i < n && nums[i] == temp[i])
          i++;
        while(j > i && nums[j] == temp[j])
          j--;
        return j-i+1;
    }
};
​

运行时间：48ms
运行内存：13.2M