题解 | #最短无序连续子数组#

题目的主要信息：

给定一个整数数组，找出一个最短的连续子数组，将这个子数组升序排列后整个数组都将是升序数组。

方法一：暴力法

遍历一遍所有子数组，用len保存符合题意的最短子数组长度。首先对子数组进行排序，然后判断该子数组排序后，整个数组否变为升序数组，如果子数组升序排列后整个数组都将是升序数组，和len中的子数组长度进行对比，保存较小的那个。

具体做法：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int len = nums.size();
        //遍历一遍所有子数组
        for(int i = 0;i<nums.size();i++){//子数组的起点
            for(int j = i;j<nums.size();j++){//子数组的终点
                vector<int> array = nums;
                sort(array.begin()+i,array.begin()+j+1);//对子数组进行排序
                int flag = true;
                //判断子数组排序后，整个数组是否变为升序数组
                for(int k = 1;k<array.size();k++){ 
                    if(array[k] < array[k-1]){//找到两个元素不为升序
                        flag = false;
                        break;
                    }
                }
                if(flag){//子数组升序排列后整个数组都将是升序数组
                    len = min(len,j-i+1);//记录最短的长度
                }
            }
        }
        if(len==1){//子数组长度为1，说明没有满足题意的子数组
            return 0;
        }else{
            return len;
        };
    }
};

复杂度分析：

• 时间复杂度：$O(n^{3}lo{g}_{2}n)O(n^3log\_2n)$，两个for循环为$O(n^2)O(n^2)$，sort函数的时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$。
• 空间复杂度：$O(n)O(n)$，array数组大小为n。

方法二：优化+排序

对方法一进行优化。用array数组复制一份nums数组，用sort函数对array数组进行排序，排序后的array数组和nums数组区别在于原来乱序的子数组经过排序后变成了有序，因此从头和尾分别开始对比array和nums中的元素，找到第一个不同的元素位置begin和最后一个不同的元素位置end，两个元素本身及它们之间的所有元素都为满足题意的子数组，子数组长度为end-begin+1。

具体做法：

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        vector<int> array = nums;
        sort(array.begin(),array.end());//排序
        int begin = 0;//数组起始位置
        int end = array.size()-1;//数组最后一个元素位置
        while(array[begin] == nums[begin]){//从头开始遍历找到第一个不同的元素
            begin++;
        }
        while(array[end] == nums[end] ){//从尾开始遍历找到第一个不同的元素
            end--;
        }
        if(end > begin){
            return end - begin + 1;//数组长度
        }else{
            return 0;
        }
    }
};

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort函数的时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$。
• 空间复杂度：$O(n)O(n)$，array数组大小为n。