最短无序连续子数组是使整个数组有序所需的最短连续子数组；通过两次扫描：左扫记录最大值并标记被“污染”位置，右扫记录最小值并标记“压制”位置，从而确定左右边界。

什么是“最短无序连续子数组”？

它指的是：对一个整数数组 nums，存在唯一最短的连续子数组，一旦将该子数组排序，整个数组就变成升序。注意不是找“最长有序前缀/后缀”，也不是找“乱序元素个数”，而是定位那个必须被重排的最小连续段。

比如 [2,6,4,8,10,9,15]，从索引 1 到 5 的子数组 [6,4,8,10,9] 排序后，整个数组有序；而更短的 [6,4] 或 [10,9] 单独排序不行——所以答案是长度 5。

两次扫描法：O(n) 时间找出左右边界

核心思路是：

• 从左往右扫，记录“当前见过的最大值”，一旦遇到比它小的数，说明这个位置必须包含在无序子数组里（因为它被前面更大的数“污染”了）；
• 从右往左扫，记录“当前见过的最小值”，一旦遇到比它大的数，说明这个位置也必须包含在无序子数组里（因为它“压住”了后面更小的数）。

int findUnsortedSubarray(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return 0;
<pre class='brush:php;toolbar:false;'>int left = -1, right = -1;
int max_so_far = nums[0], min_so_far = nums[n-1];

// 从左往右：找右边界
for (int i = 1; i < n; ++i) {
    if (nums[i] < max_so_far) {
        right = i;
    } else {
        max_so_far = nums[i];
    }
}

// 从右往左：找左边界
for (int i = n-2; i >= 0; --i) {
    if (nums[i] > min_so_far) {
        left = i;
    } else {
        min_so_far = nums[i];
    }
}

return (left == -1) ? 0 : right - left + 1;

}

立即学习“C++免费学习笔记（深入）”；

C++

"空空如也"

下载

• right 是最后一个“被前面更大值破坏升序”的位置；
• left 是第一个“破坏后面更小值升序”的位置；
• 如果全程没触发更新（left 保持 -1），说明原数组已有序，返回 0。

为什么不能只靠局部比较？常见错误在哪

很多人第一反应是：找第一个 nums[i] > nums[i+1] 和最后一个 nums[j] > nums[j+1]，然后取区间——这会漏掉跨段影响。

例如：[1,3,2,4,5,6,7,8,9,0]

• 第一个降序点是 i=1（3→2），最后一个是 j=8（9→0）；
• 但只包 [3,2,...,9] 不够：因为 0 太小，会把 1 也拉进重排范围；实际左边界是 0（整个数组都要动）。

两次扫描法通过维护极值，自动捕获这种“远端干扰”。

边界情况与性能提醒

• 空数组或单元素：直接返回 0；
• 完全逆序（如 [5,4,3,2,1]）：left=0, right=n-1，返回全长；
• 已有序：不进任何 if 分支，left 保持 -1，返回 0；
• 时间复杂度稳定 O(n)，空间 O(1)，无额外容器开销；
• 注意 max_so_far 初始化为 nums[0]，min_so_far 初始化为 nums[n-1]，否则第一次比较失效。

真正容易卡住的地方，是误以为“找到一对逆序就确定了范围”——实际上逆序对只是线索，真正边界由全局极值决定。