581. 最短无序连续子数组

一 题目：

二 思路：

分析：这个子数组有个特征

• 子数组前面的数都是升序的，且最后一个数小于子数组里的任意一个数
• 子数组后面的数都是升序的，且第一个数大于子数组里的任意一个数

因此可以分析出几个思路：
思路1：双指针+排序

• 我们可以先拷贝个数组对其排序
• 然后从左到右进行比较，第一个不同的点即为子数组起点
• 然后从右到左进行比较，第一个不同的点即为子数组终点
  时间复杂度：O(nlogn)，空间复杂度：O(n)

思路2:效率更高
同时从前往后和从后往前遍历，分别得到要排序数组的右边界和左边界；

• 寻找右边界：
  从前往后遍历的过程中，用max记录遍历过的最大值，如果max大于当前的nums[i]，说明nums[i]的位置不正确，属于需要排序的数组，因此将右边界更新为i，然后更新max；这样最终可以找到需要排序的数组的右边界，右边界之后的元素都大于max；
• 寻找左边界：
  从后往前遍历的过程中，用min记录遍历过的最小值，如果min小于当前的nums[j]，说明nums[j]的位置不正确，应该属于需要排序的数组，因此将左边界更新为j，然后更新min；这样最终可以找到需要排序的数组的左边界，左边界之前的元素都小于min；
  （从前往后遍历和从后往前遍历两个过程可以分两次循环完成，也可以放一起完成，这样的话就有：j=len-i-1）
  时间复杂度：O(n) ,空间复杂度：O(1)

三 代码:

思路1，双指针+排序

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        //拷贝份
        int[] clone = nums.clone();
        Arrays.sort(clone);

        //子数组左边界
        int left=0;
        //子数组右边届
        int right=nums.length-1;
        while (left<nums.length){
            if (nums[left]==clone[left]){
                left++;
            }else {
                break;
            }
        }

        while (right>=0){
            if (nums[right]==clone[right]){
                right--;
            }else {
                break;
            }
        }
        return right>left?right-left+1:0;
    }
}

思路2：

public int findUnsortedSubarray(int[] nums) {
        int len=nums.length;
        int max=nums[0];
        int min=nums[len-1];
        //这里right定义为-1，是为了避免数组本身有序的情况
        int left=0,right=-1;
        for (int i = 0; i < len; i++) {
            //寻找右边届
            if (max>nums[i]){
                right=i;
            }else {
                max=nums[i];
            }

            //寻找左边界
            if (min<nums[len-1-i]){
                left=len-1-i;
            }else {
                min=nums[len-1-i];
            }
        }
        return right-left+1;
    }