Leetcode 581. 最短无序连续子数组

方法1.使用JDK排序后进行对比

public int findUnsortedSubarray(int[] nums) {
    int[] sort = nums.clone();
    Arrays.sort(sort);
    int len = sort.length;
    int left  = 0;
    int right = len - 1;
    while(left < len){
        if(sort[left] == nums[left]){
            left++;
        }else{
            break;
        }
    }
    
    while(right > 0 && left < right){
        if(sort[right] == nums[right]){
            right--;
        }else{
            break;
        }
    }
    return right - left + 1;

}

方法2.类比insert sort
找到两侧的单调结束区域，对其进行遍历，如果出现其中的值小于/大于端点的值，就端点进行移动。

public int findUnsortedSubarray(int[] nums) {
    int len = nums.length;
    int i = 0;
    int j = len - 1;
    while(i < j && nums[i] <= nums[i+1]){
        i++;
    }
    while(i < j && nums[j] >= nums[j-1]){
        j--;
    }
    int m = i;
    int k = j;
    for(int a = m; a <= k; a++){
        while(i > 0 && nums[a] < nums[i-1]){
            i--;
        }
        while((j+1) < len && nums[a] > nums[j+1]){
            j++;
        }
    }
    return (j-i) == 0 ? 0 : (j-i) + 1;
}