题目主要信息

给定一个整数数组，你需要找出一个连续子数组，将这个子数组升序排列后整个数组都将是升序数组。

请你找出满足题设的最短的子数组。

方法一：排序+对比

具体方法

将数组进行排序，排序后与原数组对比，从前往后找到不相等的第一个位置$index1index1$和从后往前找到最好一个不相等的位置$index2index2$，如果 ,说明原始数组是有序的，否则返回$index2-index1+1index2\; -\; index1\; +\; 1$;

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        // write code here
        vector<int> sorts(nums);
        int len = nums.size();
        // 排序
        sort(sorts.begin(),sorts.end());
        // 看左侧第一个移动的位置
        int index1 = 0;
        while(index1<len && nums[index1] == sorts[index1])
            index1++;
        int index2 = nums.size()-1;
      // 看右侧第一个移动的位置
        while(index2>=0 && nums[index2] == sorts[index2] )
            index2--;
        if(index2 < 0)
            return 0;
        return index2-index1+1;
    }
};

复杂度分析

• 时间复杂度：$O\mathrm{（}nlo{g}_{2}n\mathrm{）}O（nlog\_2n）$,排序的时间
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$辅助数组

方法二：直接求解

具体方法

直接思考本题的话，可以发现，如果一个数大于等于左侧的数切小于等于右侧的数那么这个数是不需要移动的。

遍历数组，从左到右和从右到左记录最大值和最小值的位置。

1. 左到右，若$nums[i]\mathrm{是}nums[0:i]nums[i]是nums[0:i]$的最大值， 表示正常。如果不是最大值的情况，记录位置，当前数字需要移动。
2. 右到左，若$nums[i]\mathrm{是}nums[i:n-1]nums[i]是nums[i:n-1]$的最小值，表示正常。如果碰到了不是最小值的情况，记录位置，当前数字需要移动。

通过一次遍历完成以上两个求解，下面给出一个实例。

代码实现

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        // write code here
        int n = nums.size();
        int Max = nums[0], Min = nums[n - 1], l = -1, r = -2;
        for(int i = 1; i < n; i++){
            Max = max(Max, nums[i]);                // nums[0:i]的最大值
            Min = min(Min, nums[n - 1 - i]);      // nums[n-1-i:n-1]的最小值
            if(Max != nums[i]){
                r = i;
            }
            if(Min != nums[n - 1 - i]){
                l = n - 1 - i;
            }
        }
        return r - l + 1;
    }
};

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$,一次遍历
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$,没有额外的辅助空间