LeetCode Shortest Unsorted Continuous Subarray 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 <=.

---

给定一个数组，问最短对多长的子数组排序之后，整个数组都会是升序的。比如样例对中间的[6,4,8,10,9]这个子数组排序之后，放回到原数组，原数组也是升序排列的。 第一种解法是，直接对数组排序，然后把已排序数组和未排序数组分别从首位对比，遇到第一个不相等的位置就跳出，然后需要排序的子数组长度就是j-i+1了。 代码如下： [cpp] class Solution { public: int findUnsortedSubarray(vector<int>& nums) { vector<int> nums_copy = nums; sort(nums_copy.begin(), nums_copy.end()); int i = 0, j = nums.size() – 1; while (i <= j&&nums[i] == nums_copy[i])++i; while (j >= i&&nums[j] == nums_copy[j])–j; return j – i + 1; } }; [/cpp] 本代码提交AC，用时52MS，时间复杂度是O(nlgn)。 还有一种O(n)的方法，参考这个题解。 基本思想是这样：

1. 从左往右，如果该数已经在最终排序的位置了，那么该数必须小于等于该数右边的最小值
2. 从右往左，如果该数已经在最终排序的位置了，那么该数必须大于等于该数左边的最大值

如果违反1，那么该数右边还有比该数小的数，所以需要把这个更小的数放到该数前面，也就是说该数不在其最终的位置；违反2也是类似的。 所以我们维护两个数组，分别存储从左往右的最大值和从右往左的最小值，然后和原数组比较即可。 代码如下： [cpp] /** * /————\ * nums: [2, 6, 4, 8, 10, 9, 15] * minsf: 2 4 4 8 9 9 15 * <——————– * maxsf: 2 6 6 8 10 10 15 * ——————–> */ class Solution { public: int findUnsortedSubarray(vector<int>& nums) { int n = nums.size(); vector<int> min_so_far(n, 0), max_so_far(n, 0); for (int i = 0, maxsf = INT_MIN; i < n; ++i)max_so_far[i] = maxsf = max(maxsf, nums[i]); for (int i = n – 1, minsf = INT_MAX; i >= 0; –i)min_so_far[i] = minsf = min(minsf, nums[i]); int i = 0, j = n – 1; while (i <= j&&nums[i] <= min_so_far[i])++i; while (j >= i&&nums[j] >= max_so_far[j])–j; return j – i + 1; } }; [/cpp] 本代码提交AC，用时72MS，时间复杂度是O(n)，但是为啥比第一种方法还慢呀。]]>