佛山行业网站建设凡科建站官网登录
给定一个数组 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 = ielse: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 = ielse: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并切片即可。