给定一个数组 nums，找出最短的连续子数组，使得只要对这个子数组进行升序排序，整个数组就变为升序有序。
示例：
输入：
nums = [2, 6, 4, 8, 10, 9, 15]输出：
5（排序[6, 4, 8, 10, 9]后整个数组有序）
解法分析（最优解：O(n) 时间，O(1) 空间）
关键思路
从左到右找右边界：遍历数组，记录当前最大值
max，如果nums[i] < max，说明i应该在待排序子数组内，更新右边界right = i。从右到左找左边界：反向遍历数组，记录当前最小值
min，如果nums[i] > min，说明i应该在待排序子数组内，更新左边界left = i。计算子数组长度：
right - left + 1（如果right > left，否则数组已经有序，返回0）。
代码实现（Python）
python
复制
下载
def findUnsortedSubarray(nums):
n = len(nums)
if n <= 1:
return 0
# 初始化左右边界
left, right = n, -1
# 从左到右找右边界
max_so_far = nums[0]
for i in range(1, n):
if nums[i] < max_so_far:
right = i
else:
max_so_far = nums[i]
# 从右到左找左边界
min_so_far = nums[-1]
for i in range(n-2, -1, -1):
if nums[i] > min_so_far:
left = i
else:
min_so_far = nums[i]
return right - left + 1 if right > left else 0
复杂度分析
时间复杂度：O(n)（两次遍历数组）
空间复杂度：O(1)（仅用几个变量）
为什么这个方法有效？
右边界
right：遍历时，如果
nums[i]比当前最大值max_so_far小，说明nums[i]应该被排序，更新right = i。例如
[2, 6, 4, 8, 10, 9, 15]，max_so_far依次是2, 6, 6, 8, 10, 10，nums[5]=9 < 10，所以right=5。
左边界
left：反向遍历时，如果
nums[i]比当前最小值min_so_far大，说明nums[i]应该被排序，更新left = i。例如
min_so_far依次是15, 9, 9, 8, 4, 4，nums[1]=6 > 4，所以left=1。
最终结果：
right - left + 1 = 5 - 1 + 1 = 5（即排序[6, 4, 8, 10, 9]后整个数组有序）。
测试用例验证
| 输入 | 输出 | 解释 |
|---|---|---|
[2, 6, 4, 8, 10, 9, 15] |
5 |
排序 [6,4,8,10,9] 后整个数组有序 |
[1, 2, 3, 4] |
0 |
已经有序 |
[1] |
0 |
单元素数组 |
[5, 4, 3, 2, 1] |
5 |
整个数组需要排序 |
总结
最优解：两次遍历，分别确定左右边界，时间复杂度 O(n)，空间 O(1)。
适用场景：需要高效找到最短无序子数组的情况（如数据流分析、异常检测）。
变种问题：如果要求返回子数组本身（而非长度），只需记录
left和right并切片即可。