题目描述

主要是，需要达到 O(n) 复杂度。

思路 && 代码

1. 排序法 O(nlogn)、O(n)

诶，让我先来一个懒狗写法
先 Arrays.sort 排序，然后有序数组、原数组逐个对比，找到需要进行排序的子数组头、尾元素即可。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int[] copyArray = Arrays.copyOf(nums, len);
        // 时间复杂度 O(nlogn)
        Arrays.sort(copyArray);
        int left = 0;
        for(; left < len; left++) {
            if(nums[left] != copyArray[left]) {
                break;
            }
        }

        int right = len - 1;
        for(; right >= left; right--) {
            if(nums[right] != copyArray[right]) {
                break;
            }
        }

        return right - left + 1;
    }
}

2. 记录 max[ ]、min[ ] 的写法 O(n)、O(n）

这个思路是，之前写的接雨水，还是啥长方形题目来着…用到的思路，这里刚好套用下。
min[i]：记录 i 右边的最小元素。如果 i 比这个元素大，说明 i 需要重排。
max[i]：记录 i 左边的最大元素。如果 i 比这个元素小，说明 i 需要重排。
（实际代码复用 min数组）

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        int[] min = new int[len];
        // 1. 先找 left
        // 尾元素右边没有值，直接设为自己
        min[len - 1] = nums[len - 1];
        for(int i = len - 2; i >= 0; i--) {
            min[i] = Math.min(nums[i + 1], min[i + 1]);
        }
        int left = len - 1;
        for(int i = 0; i < len; i++) {
            if(min[i] < nums[i]) {
                left = i;
                break;
            }
        }
        if(left == len - 1) {
            return 0;
        }

        // 2. 再找 right;
        min[0] = nums[0];
        for(int i = 1; i < len; i++) {
            min[i] = Math.max(nums[i - 1], min[i - 1]);
        }
        int right = 0;
        for(int i = len - 1; i >= 0; i--) {
            if(min[i] > nums[i]) {
                right = i;
                break;
            }
        }

        return right - left + 1;
    }
}

3. 记录 max、min 的写法 O(n)、O(1)

算是方法2的优化吧，空间复杂度只有 O(1)
总体思路一样，这里是没有 break 的
max：记录 i 左边的最大元素，如果 i 更小，说明 i 需要调整
min：记录 i 右边的最大元素，如果 i 更大，说明 i 需要调整

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = nums.length;
        if(len <= 1) {
            return 0;
        }

        // 1. 从左往右，记录最大值。如果 nums[i] < max，说明 i 需要调整
        int left = -1;
        int max = nums[0];
        for(int i = 1; i < len; i++) {
            max = Math.max(max, nums[i]);
            if(nums[i] < max) {
                left = i;
            }
        }

        // 2. 从右往左，记录最小值，同理
        int right = 0;
        int min = nums[len - 1];
        for(int i = len - 2; i >= 0; i--) {
            min = Math.min(min, nums[i]);
            if(nums[i] > min) {
                right = i;
            }
        }

        // left == -1 则说明整体有序，不用排序
        return left == -1 ? 0 : left - right + 1;
    }
}