最短无序连续子数组

问题陈述

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

1
2
3
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

思路一

设置左右边界，L初始化为nums.length, R初始化为0。对数组两两比较，如果前面数大于后面数，则L=min(L, i); R=max(R,j)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {

  public int findUnsortedSubarray(int[] nums) {

​    int L=nums.length,R=0;
​    for(int i=0;i<nums.length-1;i++){
​      for(int j=i+1;j<nums.length;j++){
​        if(nums[i]>nums[j]){
​          L=Math.min(L,i);
​          R=Math.max(R,j);
​        }
​      }
​    }
​    return L>R? 0:R-L+1;
  }
}

思路二

对数组进行排序，将排序后的数组与原数组比对，发现最左最右边界。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] snums=nums.clone();
        Arrays.sort(snums);
        int R=0,L=nums.length;//注意此处L初始值
        for(int k=0;k<nums.length;k++){
            if(nums[k]!=snums[k]){
                L=Math.min(L,k);
                R=Math.max(R,k);
            }
        }
        return L>R? 0:R-L+1;
    }
}