Java 滑动窗口入门：从「长度最小的子数组」学会基础框架搭建

滑动窗口算法是处理数组或字符串子序列问题的经典技巧，尤其在优化时间和空间复杂度方面表现突出。它通过动态调整窗口大小来高效扫描数据，适用于查找满足特定条件的连续子序列。本文将以“长度最小的子数组”问题为例，手把手教你搭建Java中的滑动窗口基础框架。通过这个入门案例，你将掌握核心原理和实现步骤，为后续更复杂的应用打下坚实基础。

一、问题描述：什么是「长度最小的子数组」？

给定一个正整数数组 nums 和一个目标值 $s$，要求找到长度最小的连续子数组（即子序列），使得其元素和大于或等于 $s$。如果不存在这样的子数组，则返回 0。例如：

• 输入：nums = [2,3,1,2,4,3], $s = 7$
• 输出：子数组 [4,3] 的长度为 2（因为和 $4+3=7 \geq 7$，且无更短子数组满足条件）。

这个问题的关键在于如何快速扫描所有可能的子数组，避免暴力枚举的 $O(n^2)$ 时间复杂度。滑动窗口算法能将其优化到 $O(n)$，是理想的选择。

二、滑动窗口算法原理

滑动窗口的核心是使用两个指针（左指针 left 和右指针 right）定义一个可变窗口：

• 右指针移动：扩大窗口范围，增加当前和 $ \text{sum} $。
• 左指针移动：当窗口内和满足条件时（如 $ \text{sum} \geq s $），缩小窗口以寻找更小长度，同时更新结果。
• 动态调整：通过循环移动指针，窗口像“滑动”一样覆盖整个数组，确保每个元素只被处理一次。

这种方法的优势在于：

• 时间复杂度：$O(n)$，每个元素最多被访问两次（右指针和左指针各一次）。
• 空间复杂度：$O(1)$，仅需常数级额外空间。

三、基础框架搭建步骤

在Java中实现滑动窗口，需遵循一个通用框架。以下是针对“长度最小的子数组”问题的步骤分解：

1. 初始化变量：

   • 左指针 left = 0，右指针通过循环隐式定义。
   • 当前和 $ \text{sum} = 0$。
   • 最小长度 $ \text{minLen} = \text{Integer.MAX_VALUE}$（初始化为极大值，便于后续比较）。

2. 移动右指针：

   • 使用 for 循环遍历右指针 right，从 0 到数组末尾。
   • 每次移动，将 nums[right] 加到 $ \text{sum} $ 中，扩大窗口。

3. 检查条件并移动左指针：

   • 当 $ \text{sum} \geq s $ 时，进入 while 循环：
     • 更新最小长度：$ \text{minLen} = \min(\text{minLen}, \text{right} - \text{left} + 1)$。
     • 移动左指针：从 $ \text{sum} $ 中减去 nums[left]，然后 left++ 以缩小窗口。
   • 重复此过程，直到 $ \text{sum} < s $，确保窗口始终满足条件或最小化。

4. 处理结果：

   • 循环结束后，如果 $ \text{minLen} $ 未被更新（仍为极大值），返回 0；否则返回 $ \text{minLen} $。

这个框架通用性强，稍加修改即可应用于其他问题，如查找最大子数组或字符串子序列。

四、Java代码实现

以下是完整的Java解决方案，代码中加入了详细注释，帮助你理解每一步的逻辑：

public class MinSubArrayLen {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0; // 处理边界情况：空数组直接返回0
        }
        int left = 0; // 初始化左指针
        int sum = 0; // 当前窗口和
        int minLen = Integer.MAX_VALUE; // 最小长度，初始为极大值
        
        // 移动右指针，遍历整个数组
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right]; // 扩大窗口：将当前元素加入和
            
            // 当窗口和满足条件时（sum >= s），尝试缩小窗口以找到更小长度
            while (sum >= s) {
                minLen = Math.min(minLen, right - left + 1); // 更新最小长度
                sum -= nums[left]; // 缩小窗口：从左指针处移除元素
                left++; // 左指针右移
            }
        }
        
        // 返回结果：如果minLen未更新，说明无解；否则返回最小长度
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

代码解析：

• 初始化与边界处理：首先检查数组是否为空，避免空指针异常。
• 右指针循环：for 循环控制右指针 right 从 0 开始移动，逐步添加元素到 $ \text{sum} $。
• 左指针调整：while 循环确保当 $ \text{sum} \geq s $ 时，持续缩小窗口（通过 left++ 和减少 $ \text{sum} $），并更新 $ \text{minLen} $。
• 结果返回：使用三元运算符处理无解情况，保证鲁棒性。

运行示例：

• 输入：nums = [2,3,1,2,4,3], $s = 7$
• 输出：2（对应子数组 [4,3]）

五、扩展应用与总结

掌握了这个基础框架，你可以轻松扩展到其他滑动窗口问题：

• 变体问题：如“和大于等于 $s$ 的最大子数组”或“无重复字符的最长子串”，只需调整条件判断和更新逻辑。
• 框架通用性：核心步骤（初始化指针、移动右指针、条件检查移动左指针、更新结果）不变，是算法学习的基石。
• 练习建议：尝试在LeetCode上实践类似问题（如#209），巩固理解。

通过“长度最小的子数组”问题，你不仅学会了滑动窗口的Java实现，还搭建了一个可复用的框架。记住，算法学习重在实践——多编码、多调试，逐步提升问题解决能力。滑动窗口在数据分析和实时处理中广泛应用，是每个Java开发者必备的工具！