实战Java滑动窗口：最短无序连续子数组的窗口范围定位

问题描述

给定一个整数数组，若存在一个连续子数组，对该子数组排序后能使整个数组有序，则称该子数组为"无序子数组"。要求找到长度最短的无序子数组，并返回其长度。例如：

• 输入：$[2,6,4,8,10,9,15]$
• 输出：$5$（无序子数组为$[6,4,8,10,9]$）

核心思路

通过滑动窗口定位无序区间边界：

1. 左边界定位：从左向右扫描，记录当前最大值。当出现$nums[i] < \max$时，说明$i$位置需要调整，更新右边界$right = i$
2. 右边界定位：从右向左扫描，记录当前最小值。当出现$nums[i] > \min$时，说明$i$位置需要调整，更新左边界$left = i$
3. 窗口计算：无序子数组长度为$right - left + 1$

数学原理：设有序数组满足 $$ \forall i \in [0,n-2], \quad nums[i] \leq nums[i+1] $$ 无序子数组破坏该单调性，需满足： $$ \exists i,j \quad \text{s.t.} \quad nums[i] > \min_{j \to end},\quad nums[j] < \max_{start \to i} $$

算法实现

public int findUnsortedSubarray(int[] nums) {
    int n = nums.length;
    int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
    int left = -1, right = -1;
    
    // 定位右边界：从左向右扫描
    for (int i = 0; i < n; i++) {
        if (nums[i] < max) right = i;
        else max = nums[i];
    }
    
    // 定位左边界：从右向左扫描
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] > min) left = i;
        else min = nums[i];
    }
    
    return (left == -1) ? 0 : right - left + 1;
}

复杂度分析

• 时间复杂度：$O(n)$，两次线性扫描
• 空间复杂度：$O(1)$，仅用常量空间

案例解析

以输入$[2,6,4,8,10,9,15]$为例：

1. 定位右边界：
   • $i=0$：$max=2$
   • $i=1$：$6>2$，更新$max=6$
   • $i=2$：$4<6$ → $right=2$
   • $i=3$：$8>6$，更新$max=8$
   • $i=4$：$10>8$，更新$max=10$
   • $i=5$：$9<10$ → $right=5$
2. 定位左边界：
   • $i=6$：$min=15$
   • $i=5$：$9<15$，更新$min=9$
   • $i=4$：$10>9$ → $left=4$
   • $i=3$：$8<9$，更新$min=8$
   • $i=2$：$4<8$，更新$min=4$
   • $i=1$：$6>4$ → $left=1$
3. 结果：$5-1+1=5$

边界处理

• 完全有序数组：直接返回$0$
• 单元素无序：如$[1,3,2,4]$，窗口为$[3,2]$
• 全无序数组：窗口长度为$n$

该方法通过两次扫描精准定位无序区间，避免排序操作，是处理此类问题的经典滑动窗口实现。