581. 最短无序连续子数组

题目链接（中等）

题目描述

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

请你找出符合题意的 最短 子数组，并输出它的长度。

数据范围：

• 1 <= nums.length <= 10^4
• -10^5 <= nums[i] <= 10^5

进阶：你可以设计一个时间复杂度为 $O(n)$ 的解决方案吗？

示例

示例 1：

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

示例 2：

输入： nums = [1,2,3,4]
输出： 0

示例 3：

输入： nums = [1]
输出： 0

核心思路

可以把原数组看成三段：numsA（有序前缀）+ numsB（需要排序的部分）+ numsC（有序后缀）。目标是让 numsB 尽可能短，也就是让 numsA 和 numsC 尽可能长。

两种解法：

1. 排序比较：把 nums 排序后与原数组对比，找到第一个不同的位置 left 和最后一个不同的位置 right，返回 right - left + 1；
2. 一次遍历：通过正反两次扫描，分别确定 right 和 left，时间 $O(n)$、空间 $O(1)$。

---

方法一：排序 + 比较

思路及解法

1. 若原数组已经有序，直接返回 0；
2. 拷贝并排序 nums，得到 numsSorted；
3. 从左往右找到第一个 nums[i] != numsSorted[i] 的位置，记为 left；
4. 从右往左找到第一个 nums[i] != numsSorted[i] 的位置，记为 right；
5. 返回 right - left + 1。

为什么这样是对的？

• 排序后与原数组相同的前缀一定是已经有序的前缀；
• 排序后与原数组相同的后缀一定是已经有序的后缀；
• 中间不同的部分就是需要排序的最短子数组。

代码

from typing import List

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sorted_nums = sorted(nums)
        n = len(nums)
        
        left = 0
        while left < n and nums[left] == sorted_nums[left]:
            left += 1
        
        if left == n:  # 已经有序
            return 0
        
        right = n - 1
        while nums[right] == sorted_nums[right]:
            right -= 1
        
        return right - left + 1

复杂度分析

• 时间复杂度：$O(n \log n)$，排序需要 $O(n \log n)$，遍历 $O(n)$。
• 空间复杂度：$O(n)$，需要存储排序后的数组。

---

方法二：一次遍历（$O(n)$，推荐）

思路及解法

目标：找到最短的 [left, right]，使得 nums[left..right] 排序后整个数组有序。

性质：

• left 左侧的所有元素都满足：nums[i] <= min(nums[i+1..n-1])；
• right 右侧的所有元素都满足：nums[j] >= max(nums[0..j-1])。

确定 right：

从左往右遍历，维护已遍历部分的最大值 maxn。若当前 nums[i] < maxn，说明 nums[i] 位置不对，更新 right = i。

确定 left：

从右往左遍历，维护已遍历部分的最小值 minn。若当前 nums[i] > minn，说明 nums[i] 位置不对，更新 left = i。

代码中同时完成两次遍历：在同一个循环中用 i 从 0 到 n-1，分别从前往后和从后往前处理。

边界处理：若 right == -1，说明数组已经有序，返回 0。

举例：nums = [2,6,4,8,10,9,15]

• 正序：
  • i=0：maxn = 2
  • i=1：maxn = 6
  • i=2：4 < 6，right = 2，maxn = 6
  • i=3：maxn = 8
  • i=4：maxn = 10
  • i=5：9 < 10，right = 5
  • i=6：maxn = 15
• 逆序：
  • i=6：minn = 15
  • i=5：9 < 15，minn = 9
  • i=4：10 > 9，left = 4，minn = 9
  • i=3：8 < 9，minn = 8
  • i=2：4 < 8，minn = 4
  • i=1：6 > 4，left = 1，minn = 4
  • i=0：2 < 4，minn = 2

最终 left = 1，right = 5，长度 5，正确。

代码

class Solution:
    def findUnsortedSubarray(self, nums: list[int]) -> int:
        n = len(nums)
        maxn, right = float('-inf'), -1
        minn, left = float('inf'), -1

        for i in range(n):
            # 从左往右找右边界
            if maxn > nums[i]:
                right = i
            else:
                maxn = nums[i]

            # 从右往左找左边界
            if minn < nums[n - i - 1]:
                left = n - i - 1
            else:
                minn = nums[n - i - 1]

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

复杂度分析

• 时间复杂度：$O(n)$，仅遍历一次数组。
• 空间复杂度：$O(1)$，只用常数个变量。

---

两种方法对比

方法	时间	空间	特点
排序 + 比较	$O(n \log n)$	$O(n)$	思路直观，代码简单
一次遍历	$O(n)$	$O(1)$	满足进阶要求，效率最优

推荐：

• 面试开场：先讲排序比较，思路自然；
• 追问优化：再讲一次遍历，展示 $O(n)$ 的实现。

---

关键细节

1. 为什么排序比较能找到最短子数组

排序后与原数组相同的前缀/后缀一定是已经有序的部分，中间不同的部分必须排序。把最长的相同前缀和后缀去掉，剩下的就是最短无序子数组。

2. 一次遍历的两个方向

• 从左往右：确定右边界 right。若某个元素小于它左边所有元素的最大值，说明它需要被移动，更新 right；
• 从右往左：确定左边界 left。若某个元素大于它右边所有元素的最小值，说明它需要被移动，更新 left。

3. 为什么 right 初始为 -1

如果数组本身有序，right 不会被更新，保持 -1，此时直接返回 0。

4. 一次遍历的正确性

最终 [left, right] 之外的部分满足：

• left 左边所有元素 <= 右侧所有元素；
• right 右边所有元素 >= 左侧所有元素；

所以排序 [left, right] 后整个数组有序。而且 left 和 right 都是最靠内的边界，所以得到的子数组最短。

5. 与 LC 912（排序数组）等题的联系

本题的核心是「找出需要排序的最短区间」，与「检查数组是否有序」「寻找逆序对」等问题相关，但本题不需要真正的逆序对数量，只需要边界。

---

总结

• 核心思想：找到最短的 [left, right]，排序后整个数组有序；
• 排序法：
  • 排序后与原数组对比；
  • 找到第一个不同的位置和最后一个不同的位置；
  • 时间 $O(n \log n)$，空间 $O(n)$；
• 一次遍历法：
  • 正序扫描确定 right（维护前缀最大值）；
  • 逆序扫描确定 left（维护后缀最小值）；
  • 时间 $O(n)$，空间 $O(1)$；
• 易错点：
  • 数组已经有序时返回 0；
  • right 初始为 -1，判断有序；
  • 逆序扫描时索引是 n - i - 1。

相关题目

• LC 912. 排序数组（基础排序）
• LC 88. 合并两个有序数组（双指针）
• LC 283. 移动零（原地操作）
• LC 977. 有序数组的平方（双指针）