📃 题目描述

题目链接：581. 最短无序连续子数组 (opens new window)

🔔 解题思路

双指针 + 排序

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

        // 注意不能 int[] sorted = nums, 这是浅拷贝，sorted 的修改会影响到 nums
        int[] sorted = new int[nums.length];
        for (int i = 0; i < nums.length; i ++) {
            sorted[i] = nums[i];
        }
        Arrays.sort(sorted);

        int left = 0;
        while (left < nums.length && nums[left] == sorted[left]) {
            left ++;
        }
        // left 走到 nums.length 说明 nums 本身已经有序
        if (left == nums.length) {
            return 0;
        }

        int right = nums.length - 1;
        while (right >= 0 && nums[right] == sorted[right]) {
            right --;
        }

        return right - left + 1;
    }
}

双指针 + 一次遍历

• 中间段的最小值 > 左段的最大值
• 中间段的最大值 < 左段的最小值

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

        int left = -1;
        int right = -1;

        // 中间段的最小值
        int min = Integer.MAX_VALUE;
        // 中间段的最大值
        int max = Integer.MIN_VALUE;
        // 左段数组的最大值 < 中间段的最小值
        for (int i = nums.length - 1; i >= 0; i --) {
            if (nums[i] <= min) {
                min = nums[i];
            }
            else {
                // 如果发现 nums[i] 比当前的最小值要大，那 nums[i] 必然不可能出现在左端数组
                left = i;
            }
        }

        // 已经全局有序
        if (left == -1) {
            return 0;
        }

        for (int i = 0; i < nums.length; i ++) {
            if (nums[i] >= max) {
                max = nums[i];
            }
            else {
                // 如果发现 nums[i] 比当前的最大值要小，那么 nums[i] 必然不可能出现在右端数组
                right = i;
            }
        }

        return right - left + 1;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：