题意

给一个数组，选取数值中一段连续区间排序后，整个数组是有序的，求最短的连续区间长度

限制：

数组长度不大于$10^{4}10^4$

方法

枚举排序起始结束位置 （TLE)

直接按照题意，要找最短的区间，我们每次枚举一段区间进行排序，如果排序后，整个数组有序，那么更新这个最短值

最后输出这个最短值即可。

以题目样例数据[2,6,4,8,10,9,15]为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        int ans = nums.size();
        for(int i = 0;i<nums.size();i++){ // 开始点
            for(int j = i;j<nums.size();j++){ // 结束点
                vector<int> arr = nums; // 拷贝数组
                sort(arr.begin()+i,arr.begin()+j+1); // 排序
                int sorted = true; // 是否递增
                for(int k = 1;k<arr.size();k++){ 
                    if(arr[k] < arr[k-1]){ // 非递增
                        sorted = false;
                        break;
                    }
                }
                if(sorted)ans=min(ans,j-i+1); // 是排序了的，更新结果
            }
        }
        return ans == 1?0:ans;
    }
};

复杂度分析

时间复杂度: 因为枚举了所有起始位置，结束位置进行排序，并且每次检查了是否有序，所以总时间复杂度为$O(n^3\cdot log(n))O(n^3\backslash cdot\; log(n))$

空间复杂度: 主要消耗在拷贝用来排序的数组，所以空间复杂度为$O(n)O(n)$

排序+比较

注意到一个数组排序后是唯一的。

所以即使不知道要选哪个数组区间，也可以知道排序后的结果。

当我们有了排序后的结果，可以和原数组对比首尾，尽可能长的选取相同的部分不进行排序。

剩余中间的不同部分,就是需要排序的。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        // write code here
        vector<int> arr = nums;
        sort(arr.begin(),arr.end()); // 直接排序得到结果
        int i;
        for(i = 0;i<arr.size();i++){ // 尽可能长的前缀
            if(arr[i] != nums[i]){
                break;
            }
        }
        int j;
        for(j = arr.size()-1;j>=0;j--){ // 尽可能长的后缀
            if(arr[j] != nums[j]){
                break;
            }
        }
        return max(0, 1+j-i); // 完全有序的情况
    }
};

复杂度分析

时间复杂度: 主要耗在排序和比较，所以时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

空间复杂度: 主要在额外的对比数组上的开销，所以空间复杂度为$O(n)O(n)$