Java滑动窗口边界处理：巧妙解决「找到所有数组中消失的数字」问题

一、问题背景

在算法问题中，滑动窗口常用于处理连续子数组/子序列问题。但如何将其灵活应用于非连续场景？本文以LeetCode 448题「找到所有数组中消失的数字」为例，通过窗口边界适配技巧，实现空间复杂度$O(1)$的优雅解法。

二、问题核心需求

给定长度为$n$的数组nums，元素范围$[1, n]$，部分元素重复出现。要求：

1. 找出$[1, n]$中未出现的数字
2. 时间复杂度$O(n)$，空间复杂度$O(1)$
3. 不修改原数组（注：本文解法需轻微修改数组，但可还原）

三、滑动窗口的边界适配思路

传统滑动窗口聚焦连续区间，而本题需处理离散数值。核心创新点：

1. 将数值映射为索引：利用$ \text{index} = |\text{num}| - 1 $ 将数字关联到数组位置
2. 窗口标记法：遍历数组时，通过取负操作标记出现过的数字
3. 边界保护：索引计算需严格满足$ 0 \leq \text{index} < n $

数学表达：
$$
\text{标记规则：} \quad \text{nums}[|x|-1] \rightarrow -\text{nums}[|x|-1]
$$
$$
\text{边界约束：} \quad \forall x \in \text{nums}, \ 1 \leq |x| \leq n
$$

四、边界处理关键代码

public List<Integer> findDisappearedNumbers(int[] nums) {
    // 第一轮遍历：标记出现过的数字
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1; // 关键边界映射
        if (nums[index] > 0) {  // 避免重复取负
            nums[index] = -nums[index];
        }
    }
    
    // 第二轮遍历：收集未标记的索引
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            result.add(i + 1);  // 索引转回数值
        } else {
            nums[i] = -nums[i]; // 还原数组
        }
    }
    return result;
}

五、边界处理详解

1. 索引越界防护

   • 通过Math.abs(nums[i]) - 1确保索引$ \in [0, n-1] $
   • 因$ \text{nums}[i] \in [1, n] $，故索引天然合法

2. 重复操作防护

   • 条件if (nums[index] > 0)避免重复标记导致值反转

3. 数据还原设计

   • 收集结果后执行nums[i] = -nums[i]还原数组原始值

六、复杂度与适用场景

七、总结

通过数值→索引的边界映射和取负标记法，滑动窗口思想成功适配离散值统计场景。该解法体现了三大优势：

1. 严格满足空间复杂度$O(1)$约束
2. 边界处理清晰且无冗余操作
3. 代码简洁，可扩展至类似问题（如「数组中重复的数据」）

启示：算法思想的应用需跳出固定模式，通过边界适配将工具灵活迁移至新场景。