题目描述

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 <=.

题意 ：给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。

算法1

(排序) $O(nlogn)$

题解1:排序，然后分别找到两端已经排好序的长度。中间那部分就是需要重新排列的长度。时间复杂度$O(nlogn)$，空间复杂度$O(n)$。

    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> temp;
        temp.assign(nums.begin(),nums.end());
        sort(temp.begin(),temp.end());
        int n = nums.size(),left = 0,right = n - 1;
        while(left < n && nums[left] == temp[left]) left ++;
        while(right >= left && nums[right] == temp[right]) right --;
        return right - left + 1;
    }

算法2

(扫描) $O(n)$

题解2：整体思路和题解1其实是类似的，找到两段已经排好序的长度。我们先使用一遍扫描找到左边保持升序的最后一个点的位置left,和从右向左看保持降序的最后一个点的位置right。如果已经这时候left == right说明已经排好序了，无需调整。接下来我们从left + 1的位置向右扫描，如果遇到有比nums[left]小的元素，说明最起码left不在正确位置上，那么left —。同样的，我们从right - 1的位置向左扫描，如果遇到有比nums[right]大的元素，说明最起码nums[right]不在正确的位置上，right ++。最后，left和right之间的元素就是需要重新排序的元素，长度为right - left - 1。

时间复杂度$O(n)$,空间复杂度$O(1)$。

    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size(),left = 0,right = n - 1;
        if(n == 1) return 0;
        while(left < n - 1 && nums[left + 1] >= nums[left]) left ++;
        while(right > left && nums[right] >= nums[right - 1]) right --;
        if(right == left) return 0;
        for(int i = left + 1 ; i < n ; i ++)
            while(left >= 0 && nums[i] < nums[left])
                left --;
        for(int i = right - 1 ; i >= 0 ; i --)
            while(right < n && nums[i] > nums[right])
                right ++;
        return right - left - 1;
    }