581. 最短无序连续子数组
题目描述
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例
示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：只需要对 [6,4,8,10,9] 进行排序
示例 2：
输入：nums = [1,2,3,4]
输出：0
解题思路
第一步：理解问题本质
需要找到最短的连续子数组，排序后整个数组有序。关键问题是：如何确定这个子数组的边界？
第二步：排序对比法
将数组排序，对比原数组和排序后的数组，找出第一个和最后一个不同位置。
缺点：需要 O(n log n) 时间，O(n) 额外空间。
第三步：双指针一次遍历（最优）
核心洞察：
- 从左向右遍历，维护最大值
maxn。如果nums[i] < maxn，说明i位置需要调整，更新右边界right - 从右向左遍历，维护最小值
minn。如果nums[n-1-i] > minn，说明该位置需要调整，更新左边界left
完整代码实现
算法可视化 · 逐帧回放这道题的代码41 帧 · 录制输入 [2,6,4,8,10,9,15]
from typing import List
class Solution:
"""
最短无序连续子数组 - 双指针一次遍历
从左向右找右边界：维护最大值，当前值小于最大值则需要排序
从右向左找左边界：维护最小值，当前值大于最小值则需要排序
时间复杂度：O(n)
空间复杂度：O(1)
"""
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
示例推演
以 nums = [2,6,4,8,10,9,15] 为例：
| i | nums[i] | maxn | right | nums[n-1-i] | minn | left |
|---|---|---|---|---|---|---|
| 0 | 2 | 2 | -1 | 15 | 15 | -1 |
| 1 | 6 | 6 | -1 | 9 | 9 | -1 |
| 2 | 4 | 6 | 2 | 10 | 9 | 4 |
| 3 | 8 | 8 | 2 | 8 | 8 | 4 |
| 4 | 10 | 10 | 2 | 4 | 4 | 4 |
| 5 | 9 | 10 | 5 | 6 | 4 | 1 |
| 6 | 15 | 15 | 5 | 2 | 2 | 1 |
- 向右扫：
maxn记录此前最大值。nums[2] = 4 < maxn = 6，说明 4 的位置偏后，right = 2； 到nums[5] = 9 < maxn = 10，right继续右移到 5。 - 向左扫：
minn记录右侧最小值。nums[4] = 10 > minn = 9，说明 10 的位置偏前，left = 4； 到nums[1] = 6 > minn = 4，left继续左移到 1。
最终 left = 1、right = 5，长度 5 - 1 + 1 = 5，对应子数组 [6,4,8,10,9]。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 排序对比 | O(n log n) | O(n) | 需要排序 |
| 双指针（最优） | O(n) | O(1) | 一次遍历 |
易错点总结
1. 边界条件
如果数组已有序，right 保持 -1，返回 0。