581. Shortest Unsorted Continuous Subarray.md

581. Shortest Unsorted Continuous Subarray

思路

给定整数数组，找到一个最短的连续子数组(满足条件：若将该子数组排序则整个数组都将有序)，返回子数组的长度。

思路一

将原数组排序，再从前往后遍历并与排序前比较，第一个和最后一个元素不同的位置索引即为子数组的界限。
时间复杂度O(nlogn)

思路二

若该子数组为nums[left,left+1,...,right], 那么nums[0,1,...,left-1]将递增有序，nums[right+1,...,n-1]也递增有序。
而且nums[left-1]小于其右边的所有数，nums[right+1]大于其右边的所有数。
可以用以下步骤找到left和right:

• 1.从前往后遍历直到不满足有序，将找到left的上界low(left <= low);
• 2.从后往前遍历直到不满足有序，将找到right的下界high(right >= high);
• 3.找到nums[low+1, ..., n-1]中的最小值right_min, 找到nums[0,...,high-1]的最大值left_max;
• 4.在nums[0,...low]中从前往后找到第一个大于right_min的元素，其下标即left;
• 5.在nums[high,...,n-1]中从后往前找到第一个小于left_max的元素，其下标即right。

注意：

• 由于low <= high, 所以在进行第1、2步时可以顺便进行第3步(的一部分)；
• 4、5两步由于是在有序表中查找，所以用二分查找更快。

C++

思路二

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int left, right;
        int low = 0, high = nums.size() - 1;
        int right_min = nums[nums.size() - 1], left_max = nums[0];
        // 步骤1
        while((low < nums.size() - 1) && nums[low] <= nums[low + 1]) {
            if(nums[low] > left_max) left_max = nums[low]; // 顺便做步骤3
            low++;
        }
        if(low ==  nums.size() - 1) return 0; // 整个元素已经有序
        // 步骤2
        while(high > 1 && nums[high] >= nums[high - 1]) {
            if(nums[high] < right_min) right_min = nums[high]; // 顺便做步骤3
            high--;
        }
        
        // 完成步骤3的剩下部分
        for(int i = low; i <= high; i++){
            if(nums[i] < right_min) right_min = nums[i];
            if(nums[i] > left_max) left_max = nums[i];
        }
        
        // 步骤4：二分查找
        int find_low = 0, find_high = low;
        int mid;
        while(find_low <= find_high){
            mid = (find_low + find_high) / 2;
            if(nums[mid] <= right_min) find_low = mid + 1;
            else find_high = mid - 1;
        }
        left = find_low;
         
        // 步骤5：二分查找
        find_low = high;
        find_high = nums.size() - 1;
        while(find_low <= find_high){
            mid = (find_low + find_high) / 2;
            if(nums[mid] >= left_max) find_high = mid - 1;
            else find_low = mid + 1;
        }
        right = find_high;

        return right - left + 1;
    }
};