题目描述
思路解析
一句话答案：LeetCode 581 最短无序连续子数组的最优解是两遍线性扫描：从左往右，凡是比「此前最大值」还小的位置都必须重排，最右的一个就是右边界；从右往左对称地用「此后最小值」定左边界。时间 O(n)、空间 O(1)，比排序后逐位比对的 O(n log n) 更优。
这道题真正在问什么
给一个整数数组，找出最短的一段连续子数组，使得只把这一段升序排序后，整个数组就有序，返回这段的长度；数组本来就有序时返回 0。注意求的是长度不是内容，而且这段必须连续——问题实质是定位两个边界：最左边那个必须动的位置，和最右边那个必须动的位置，答案就是两者的距离加一。
排序后逐位比对为什么不是最优解
最直观的做法：把数组复制一份排好序，和原数组逐位比对，左起第一个不同的位置是左边界、右起第一个不同的位置是右边界。这个思路完全正确，但排序花掉 O(n log n) 时间、副本花掉 O(n) 空间，都是浪费——我们并不需要知道排好后每个位置具体是什么数，只需要判断「哪些位置不在它该在的地方」，而这个判断有更便宜的办法。
什么样的位置一定要被重排
换个角度看「有序」的定义：数组升序，等价于每个数都不小于它左边的所有数。所以从左往右扫，维护一个「到目前为止的最大值 maxv」，一旦当前数比 maxv 还小，说明左边有更大的数压着它，这个位置必须被卷进重排区间。所有这样的位置里最靠右的那个，就是右边界 right——right 右边的数全都不小于左侧最大值，本来就各就各位。
左边界完全对称：升序也等价于每个数都不大于它右边的所有数。从右往左扫，维护「此后最小值 minv」，凡是比 minv 还大的位置都必须动，其中最靠左的那个就是左边界 left。
为什么必须分两遍、方向相反地扫
右边界依赖「从左到右一路累积的最大值」，左边界依赖「从右到左一路累积的最小值」——两个量的累积方向相反，一趟单向扫描只攒得出其中一个，所以必须各扫一遍。两遍都是不嵌套的纯线性扫描，总时间仍是 O(n)，并没有因为多扫一遍而升级复杂度。
复杂度与最容易翻车的边界
时间 O(n)：两趟线性扫描各走一遍数组。空间 O(1)：只用 maxv、minv、left、right 四个变量，不开副本。最容易翻车的边界是数组本来就有序：这时第一遍扫描里永远不会出现「当前数小于 maxv」，right 保持初值 -1，必须直接返回 0，忘了这个判断就会拿未更新的边界算出荒谬的长度。另外相等元素不算乱：判断用的是严格小于和严格大于，像 [1,2,2,3] 这种带重复值的有序数组会正确地返回 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条「从左找最右的乱点定右界、从右找最左的乱点定左界」，下面每帧都在套它。
当前处理下标 0，值 1，它不小于前面的最大值，反而刷新了最大值到 1——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
当前处理下标 1，值 3，它不小于前面的最大值，反而刷新了最大值到 3——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
当前处理下标 2，值 2，它比前面见过的最大值 3 还小——说明它本该排到前面去，是乱的。于是把右边界 right 拉到下标 2。右边界会一直被后面更靠右的乱点刷新，所以最终停在「最后一个乱点」。
当前处理下标 3，值 2，它比前面见过的最大值 3 还小——说明它本该排到前面去，是乱的。于是把右边界 right 拉到下标 3。右边界会一直被后面更靠右的乱点刷新，所以最终停在「最后一个乱点」。
当前处理下标 4，值 5，它不小于前面的最大值，反而刷新了最大值到 5——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
当前处理下标 5，值 7，它不小于前面的最大值，反而刷新了最大值到 7——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
当前处理下标 6，值 6，它比前面见过的最大值 7 还小——说明它本该排到前面去，是乱的。于是把右边界 right 拉到下标 6。右边界会一直被后面更靠右的乱点刷新，所以最终停在「最后一个乱点」。
当前处理下标 7，值 8，它不小于前面的最大值，反而刷新了最大值到 8——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
当前处理下标 8，值 4，它比前面见过的最大值 8 还小——说明它本该排到前面去，是乱的。于是把右边界 right 拉到下标 8。右边界会一直被后面更靠右的乱点刷新，所以最终停在「最后一个乱点」。
当前处理下标 9，值 9，它不小于前面的最大值，反而刷新了最大值到 9——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
当前处理下标 10，值 10，它不小于前面的最大值，反而刷新了最大值到 10——到这里为止都是顺的，没越位。右边界不动，继续往右扫。
第一遍扫完：右边界 right 停在下标 8（这是最靠右的那个乱点）。它右边的 [9, 10] 都顺、不用动。接下来反过来从右往左扫，定左边界。
当前处理下标 10，值 10，它不大于后面的最小值，反而刷新了最小值到 10——从右边看到这里都是顺的。左边界不动，继续往左扫。
当前处理下标 9，值 9，它不大于后面的最小值，反而刷新了最小值到 9——从右边看到这里都是顺的。左边界不动，继续往左扫。
当前处理下标 8，值 4，它不大于后面的最小值，反而刷新了最小值到 4——从右边看到这里都是顺的。左边界不动，继续往左扫。
当前处理下标 7，值 8，它比后面见过的最小值 4 还大——说明它本该排到后面去，是乱的。于是把左边界 left 拉到下标 7。左边界会被更靠左的乱点不断刷新，最终停在「第一个乱点」。
当前处理下标 6，值 6，它比后面见过的最小值 4 还大——说明它本该排到后面去，是乱的。于是把左边界 left 拉到下标 6。左边界会被更靠左的乱点不断刷新，最终停在「第一个乱点」。
当前处理下标 5，值 7，它比后面见过的最小值 4 还大——说明它本该排到后面去，是乱的。于是把左边界 left 拉到下标 5。左边界会被更靠左的乱点不断刷新，最终停在「第一个乱点」。
当前处理下标 4，值 5，它比后面见过的最小值 4 还大——说明它本该排到后面去，是乱的。于是把左边界 left 拉到下标 4。左边界会被更靠左的乱点不断刷新，最终停在「第一个乱点」。
当前处理下标 3，值 2，它不大于后面的最小值，反而刷新了最小值到 2——从右边看到这里都是顺的。左边界不动，继续往左扫。
当前处理下标 2，值 2，它不大于后面的最小值，反而刷新了最小值到 2——从右边看到这里都是顺的。左边界不动，继续往左扫。
当前处理下标 1，值 3，它比后面见过的最小值 2 还大——说明它本该排到后面去，是乱的。于是把左边界 left 拉到下标 1。左边界会被更靠左的乱点不断刷新，最终停在「第一个乱点」。
当前处理下标 0，值 1，它不大于后面的最小值，反而刷新了最小值到 1——从右边看到这里都是顺的。左边界不动，继续往左扫。
两遍扫完：左边界 left=1、右边界 right=8。绿色这段 [3, 2, 2, 5, 7, 6, 8, 4] 就是要排的最短子数组，长度 8；两侧灰色部分本就有序、不用动。只扫两遍，O(n) 时间、O(1) 额外空间。
边界先想清：完全有序返回 0、完全乱序返回 n，本算法都能正确处理。
两个高频追问：对比排序法的 O(n log n)，并解释「为什么必须分两遍」。
参考代码
def findUnsortedSubarray(nums): n = len(nums) maxv, right = float("-inf"), -1 for i in range(n): # 从左扫找右边界 if nums[i] < maxv: right = i # 比前面最大值还小=乱 else: maxv = nums[i] minv, left = float("inf"), n for i in range(n - 1, -1, -1): # 从右扫找左边界 if nums[i] > minv: left = i # 比后面最小值还大=乱 else: minv = nums[i] return 0 if right == -1 else right - left + 1复杂度
- 时间：O(n)，两遍线性扫描，各走一趟数组
- 空间：O(1)，只用 maxv/minv/left/right 几个变量，不开新数组
易错点
面试追问把动画讲成自己的话
追问最直观的解法是什么？复杂度如何？
追问为什么两遍扫描各只能定一个边界，不能合并成一遍？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
字符串转换整数 (atoi)
LeetCode 8 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题