C++ 解法, 执行用时: 4ms, 内存消耗: 640KB, 提交时间: 2021-11-22

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        // write code here
        vector<int> tmp = nums;
        sort(tmp.begin(),tmp.end());
        int start = 0,finall = tmp.size()-1;
        while(tmp[start] == nums[start]) start++;
        while(tmp[finall] == nums[finall] ) finall--;
        if(finall > start)
            return finall - start + 1;
        else return 0;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 644KB, 提交时间: 2022-02-11

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int maxn = INT_MIN;
        int minn = INT_MAX; 
        int left = -1;
        int right = -1;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(maxn > nums[i]) //更新区间
                right = i;
            else //更新最大值
                maxn = nums[i];
            if(minn < nums[n - i - 1]) //更新区间
                left = n - i - 1;
            else //更新最小值
                minn = nums[n - i - 1];
        }
        return right == -1 ? 0 : right - left + 1; //right到-1就是整个数组都有序
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 660KB, 提交时间: 2022-02-19

class Solution {
public:
    int findUnsortedSubarray(vector<int>& nums) {
        int maxn = INT_MIN;
        int minn = INT_MAX; 
        int left = -1;
        int right = -1;
        
        int n = nums.size();
        for(int i = 0; i < n; i++)
        {
            if(maxn > nums[i])
                right = i;
            else
                maxn = nums[i];
            
            if(minn < nums[n - i - 1])
                left = n - i - 1;
            else 
                minn = nums[n - i - 1];
        }
        
        return right == -1 ? 0 : right - left + 1;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 668KB, 提交时间: 2022-02-09

class Solution {
public:
    /*
    题意整理
    1. 给定一个整数数组，找出一个连续子数组，将这个子数组升序排列后整个数组都变为升序数组。
    2. 求满足条件的最短的连续子数组的长度。
    
    方法一：排序
    
    解题思路
    1. 首先定义一个新数组arr，将原数组的值复制到新数组。
    2. 对原数组nums进行排序。
    3. 从前往后，找到第一个不相等的元素位置，记为子数组的起点。
       从后往前，找到第一个不相等的元素位置，记为子数组的终点。
       计算起点、终点距离，即可知道对应子数组的长度。
    
    复杂度分析
    时间复杂度：需要对数组进行排序，以及遍历整个数组，排序的时间复杂度为O(nlog2n)，
              遍历的时间复杂度为O(n)，所以时间复杂度是O(nlog2n)
    空间复杂度：需要额外大小为n的arr数组，所以空间复杂度为O(n)
    */
    int findUnsortedSubarray1(vector<int>& nums) {
        int n = nums.size(); //数组长度
        vector<int> arr(nums); //复制原数组到arr数组
        sort(nums.begin(), nums.end()); //对应原数组nums进行排序
        //start记录最短无序连续子数组的起点。end记录对应的终点
        int start = -1, end = -1;
        for(int i=0; i<n; i++){
            //如果不相等，将i标记为起点，并结束循环
            if(arr[i] != nums[i]){
                start = i;
                break;
            }
        }
        for(int i=n-1; i>=0; i--){
            //如果不相等，将i标记为终点，并结束循环
            if(arr[i] != nums[i]){
                end = i;
                break;
            }
        }
        //如果所有元素都相等，直接返回0，否则返回对应长度
        return (start==-1 && end==-1) ? 0: end-start+1;
    }
    
    /*
    方法二：贪心
    
    解题思路
    1. 首先找到使得数组无序的对应位置最小值，以及使得数组无序的对应位置最大值
    2. 然后找第一个大于最小值的位置，必定是子数组的起点，而前面的数都小于这个最小值
    3. 接着从后往前找第一个小于最大值的位置，必定是子数组的终点，而后面的数都大于这个最大值
    4. 所以起点、终点之间一定是最短无序的连续子数组
    
    复杂度分析
    时间复杂度：需要对原数组进行4次遍历，每次都只有一层循环，所以时间复杂度是O(n)
    空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为O(1)
    */
    int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size(); //数组长度
        //startNum记录最短无序连续子数组的最小值，endNum记录对应的最大值
        int startNum=100001, endNum=-1;
        //start记录最短无序连续子数组的起点。end记录对应的终点
        int start=-1, end=-1;
        for(int i=1; i<n; i++){
            if(nums[i] < nums[i-1]){
                startNum = min(startNum, nums[i]);
            }
        }
        for(int i=0; i<n; i++){
            //如果大于startNum，说明是子数组的起点
            if(nums[i] > startNum){
                start = i;
                break;
            }
        }
        for(int i=n-2; i>=0; i--){
            if(nums[i] > nums[i+1]){
                endNum = max(endNum, nums[i]);
            }
        }
        for(int i=n-1; i>=0; i--){
            //如果小于endNum，说明是子数组的终点
            if(nums[i] < endNum){
                end = i;
                break;
            }
        }
        //如果所有元素都相等，直接返回0，否则返回对应长度
        return (start==-1 && end==-1) ? 0 : end-start+1;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 776KB, 提交时间: 2021-12-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int findUnsortedSubarray(vector<int>& nums) {
        // write code here
             vector<int> tmp = nums;
        sort(tmp.begin(),tmp.end());
        int start = 0,finall = tmp.size()-1;
        while(tmp[start] == nums[start]) start++;
        while(tmp[finall] == nums[finall] ) finall--;
        if(finall > start)
            return finall - start + 1;
        else return 0;
    }
};