Java 滑动窗口入门题：「二进制子数组的个数」的窗口计数方法

滑动窗口算法是处理数组问题的核心技巧之一，特别适合计算连续子数组满足特定条件的场景。在Java编程中，掌握这一方法能显著提升算法解决能力。本文将以“二进制子数组的个数”为例，详细讲解滑动窗口计数方法的原理和实现。问题定义为：给定一个二进制数组（元素仅为0或1），计算所有子数组中和等于指定整数$K$的个数。例如，数组$[0,1,0,1]$中，$K=2$时，满足条件的子数组有$[1,0,1]$和$[0,1,0,1]$，因此个数为2。我们将从基础概念入手，逐步构建Java解决方案。

滑动窗口原理

滑动窗口通过动态调整一个“窗口”（即连续子数组）来避免重复计算，核心是使用两个指针：左指针$l$和右指针$r$，表示窗口的起始和结束位置。定义数组为$A$，长度为$n$，元素为$A[i]$（$i$从0开始）。窗口和$S$计算为： $$S = \sum_{i=l}^{r} A[i]$$ 目标是使$S = K$，并统计所有满足条件的$[l, r]$对。算法步骤如下：

1. 初始化$l = 0$，$S = 0$，计数变量$count = 0$。
2. 右指针$r$从0遍历到$n-1$，每次将$A[r]$加入$S$。
3. 如果$S > K$，则移动左指针$l$，减少$S$，直到$S \leq K$。
4. 如果$S = K$，则$count$增加1。
5. 重复步骤2-4，直到$r$遍历完成。 此方法时间复杂度为$O(n)$，空间复杂度为$O(1)$，适用于非负数组（二进制数组满足此条件）。

Java代码实现

以下是一个完整的Java程序，实现滑动窗口计数方法。代码包含详细注释，帮助理解每一步逻辑。

public class BinarySubarrayCounter {
    /**
     * 计算二进制数组中子数组和等于K的个数
     * @param nums 二进制数组，元素为0或1
     * @param k 目标值
     * @return 满足条件的子数组个数
     */
    public static int countSubarrays(int[] nums, int k) {
        int count = 0;        // 初始化计数
        int left = 0;         // 左指针
        int currentSum = 0;   // 当前窗口和
        
        // 右指针遍历数组
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];  // 添加右指针元素到和
            
            // 如果和超过K，移动左指针减少和
            while (currentSum > k && left <= right) {
                currentSum -= nums[left];
                left++;
            }
            
            // 检查当前和是否等于K
            if (currentSum == k) {
                count++;
            }
        }
        return count;
    }
    
    // 主方法测试示例
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 1};  // 示例数组
        int k = 2;                  // 目标K值
        int result = countSubarrays(nums, k);
        System.out.println("子数组个数: " + result);  // 输出应为2
    }
}

逐步解析代码

1. 初始化变量：

   • count：用于记录满足$S = K$的子数组个数，初始为0。
   • left：左指针，表示窗口起始位置，初始为0。
   • currentSum：当前窗口和，初始为0。

2. 遍历数组：

   • 使用right指针从0开始遍历数组（right作为窗口结束位置）。
   • 每次迭代，将nums[right]加入currentSum（因为数组元素为0或1，添加操作简单）。

3. 调整窗口大小：

   • 如果currentSum > k，说明窗口和过大，需要移动左指针缩小窗口。
   • 使用while循环：从currentSum中减去nums[left]，并递增left，直到currentSum <= k。

4. 检查并计数：

   • 在调整窗口后，如果currentSum == k，则递增count。
   • 此步骤确保只计数有效子数组，且每次右指针移动后只检查一次。

5. 返回结果：

   • 遍历完成后，count即为所求值。

复杂度分析

• 时间复杂度：$O(n)$，其中$n$为数组长度。每个元素最多被左指针和右指针各访问一次。
• 空间复杂度：$O(1)$，仅使用常数级额外空间（无额外数据结构）。

边界处理与注意事项

• 数组元素特性：二进制数组元素非负（0或1），因此滑动窗口方法有效。如果数组包含负数，需其他方法如前缀和+哈希表。
• $K=0$情况：本实现未处理$K=0$，因为二进制数组中和为0的子数组通常是全0子数组。实际应用中，可扩展逻辑：当$K=0$时，计数窗口和恰好为0的子数组。
• 测试用例：
  • 输入nums = [1,0,1,0,1], k = 2，输出应为3（子数组[1,0,1]、[0,1,0,1]等）。
  • 输入nums = [0,0,0], k = 0，输出应为6（所有子数组和均为0）。

总结

通过本入门题，我们学习了Java中滑动窗口算法的核心应用：维护动态窗口、指针移动策略和条件计数。此方法可扩展到其他问题，如计算子数组最大和或处理字符串子序列。实践中，建议多练习变种题目（如LeetCode相关题）以加深理解。滑动窗口不仅提升代码性能，还能培养对数组问题的直观洞察力。