最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

• 来源：力扣（LeetCode）
• 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray

数据范围

1 <= nums.length <= 104
-105 <= nums[i] <= 105

示例一

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例二

输入：nums = [1,2,3,4]
输出：0

示例三

输入：nums = [1]
输出：0

思路一

新建一个数组，并排序，使用双指针，分别由前往后，有后往前，找到与愿数组第一个不同的下表记录，即找到需要排序的范围

AC代码一

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

思路二

三段处理，一三两端是不用排序的，中间一段是需要排序的。

我们先找到第一个不符合升序的下标i，在找到最后一个不符合升序的下标j，这就简单分成了三段

第一段 [0,i), 第二段[i,j], 第三段(j,n].
之后我们遍历第二段，遍历下标先用x代替

• 若nums[x] < nums[i],在整体排序中，nums[x]应出现在nums[i] 前面，所以 i 应 -1
• 若nums[x] > nums[j],在整体排序中，nums[x]应出现在nums[j] 后面，所以 j 应 +1

最后我们得到i,j。其中需要排序的片段是(i,j)，

• 若i != j,所以结果应为 (j-1)-(i+1)+1;
• 若i = j，结果为 0.

另，借助哨兵，进行一些细微调整。

AC代码二

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int MAX = 100005,MIN = -100005;
        int i = 0,j = nums.size() - 1;
        while(i < j && nums[i] <= nums[i+1]) i++;
        while(i < j && nums[j] >= nums[j-1]) j--;
        int l = i,r = j;
        int min = nums[i],max = nums[j];
        for(int x = l;x <= r;x++){
            if(nums[x] < min){
                while(i >= 0 && nums[x] < nums[i])i--;
                min = i >= 0 ?nums[i]:MIN;
            }
            if(nums[x] > max){
                while(j < nums.size() && nums[x] > nums[j])j++;
                max = j < nums.size()?nums[j]:MAX;
            }
        }
        return i == j ? 0 : (j - 1) - (i + 1) + 1;
    }
};