最短无序连续子数组

问题拆解

要找出最短的连续子数组，只要把它排好序，整个数组就有序，返回它的长度。

一个很自然的做法：把数组复制一份排序，再从两端向中间比对，第一处和最后一处与原数组不同的位置就框定了无序段。它正确、好写，但排序带来 O(n log n) 的时间。进阶希望做到 O(n)，就得想清楚：到底是什么让一个元素“必须被重排”。

如果某个元素比它左边出现过的最大值还小，它就站错了位置，无序段的右边界至少要到它这里；对称地，比右边最小值还大的元素，界定了左边界。

排序后比对（作为对照）

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

def findUnsortedSubarray(nums):
    sorted_nums = sorted(nums)
    left, right = 0, len(nums) - 1
    while left <= right and nums[left] == sorted_nums[left]:
        left += 1
    while right >= left and nums[right] == sorted_nums[right]:
        right -= 1
    return right - left + 1

func findUnsortedSubarray(nums []int) int {
    sorted := append([]int(nil), nums...)
    slices.Sort(sorted)
    left, right := 0, len(nums)-1
    for left <= right && nums[left] == sorted[left] {
        left++
    }
    for right >= left && nums[right] == sorted[right] {
        right--
    }
    return right - left + 1
}

pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
    let mut sorted = nums.clone();
    sorted.sort_unstable();
    let mut left = 0i64;
    let mut right = nums.len() as i64 - 1;
    while left <= right && nums[left as usize] == sorted[left as usize] {
        left += 1;
    }
    while right >= left && nums[right as usize] == sorted[right as usize] {
        right -= 1;
    }
    (right - left + 1) as i32
}

这版本把“哪里开始乱、哪里结束”交给排序去回答，思路清楚，适合先建立直觉。瓶颈只在排序的 O(n log n)。

两趟扫描定位边界

从左往右维护“到目前为止的最大值” max_seen：一旦当前元素比它小，说明这个元素被更大的数越过了，把右边界 right 更新到这里。从右往左维护“到目前为止的最小值” min_seen：当前元素比它大，就把左边界 left 更新到这里。

public int findUnsortedSubarray(int[] nums) {
    int n = nums.length;
    int right = -1;
    int maxSeen = nums[0];
    for (int i = 0; i < n; i++) {
        if (nums[i] < maxSeen) {
            right = i;
        } else {
            maxSeen = nums[i];
        }
    }

    int left = n;
    int minSeen = nums[n - 1];
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] > minSeen) {
            left = i;
        } else {
            minSeen = nums[i];
        }
    }

    return right == -1 ? 0 : right - left + 1;
}

def findUnsortedSubarray(nums):
    n = len(nums)
    right = -1
    max_seen = nums[0]
    for i in range(n):
        if nums[i] < max_seen:
            right = i
        else:
            max_seen = nums[i]

    left = n
    min_seen = nums[-1]
    for i in range(n - 1, -1, -1):
        if nums[i] > min_seen:
            left = i
        else:
            min_seen = nums[i]

    return right - left + 1 if right != -1 else 0

func findUnsortedSubarray(nums []int) int {
    n := len(nums)
    right := -1
    maxSeen := nums[0]
    for i := 0; i < n; i++ {
        if nums[i] < maxSeen {
            right = i
        } else {
            maxSeen = nums[i]
        }
    }

    left := n
    minSeen := nums[n-1]
    for i := n - 1; i >= 0; i-- {
        if nums[i] > minSeen {
            left = i
        } else {
            minSeen = nums[i]
        }
    }

    if right == -1 {
        return 0
    }
    return right - left + 1
}

pub fn find_unsorted_subarray(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut right: i32 = -1;
    let mut max_seen = nums[0];
    for i in 0..n {
        if nums[i] < max_seen {
            right = i as i32;
        } else {
            max_seen = nums[i];
        }
    }

    let mut left = n as i32;
    let mut min_seen = nums[n - 1];
    for i in (0..n).rev() {
        if nums[i] > min_seen {
            left = i as i32;
        } else {
            min_seen = nums[i];
        }
    }

    if right == -1 { 0 } else { right - left + 1 }
}

两遍扫描各自找到最靠右的“偏小元素”和最靠左的“偏大元素”，它们之间就是必须重排的区间。以 [2,6,4,8,10,9,15] 为例：从左看 4、9 依次小于此前的最大值，右边界停在下标 5；从右看 10、6 依次大于其右侧最小值，左边界停在下标 1，区间长度 5 - 1 + 1 = 5。若数组本就有序，第一趟不会更新 right，它保持初始的 -1，直接返回 0。

复杂度

指标	复杂度	原因
时间	`O(n)`	左右各扫一遍
空间	`O(1)`	只维护边界与极值

可以迁移的模式

需要判断“哪些元素破坏了单调性”；
一个方向的信息不够，就正反两趟分别维护历史极值；
用越界元素反推区间边界，避免真的去排序。

“最多交换一段使数组有序”“判断能否通过一次翻转变有序”都能借这种双向扫描的视角来想。