滑动窗口与前缀和：从和为 K 到最小覆盖子串

1. 题目一：和为 K 的子数组 (LeetCode 560)

题目背景

这道题虽然被归类在子串/子数组中，但它是'滑动窗口'思想的变体——前缀和 + 哈希表。当子数组包含负数时，标准的滑动窗口无法工作，必须借助前缀和。

核心技巧：前缀和思想

• 定义为范围内的元素之和。
• 任意子数组的和可以表示为 prefix[i] - prefix[j]。
• 我们需要寻找满足 prefix[i] - prefix[j] = k 的个数，等价于 prefix[j] = prefix[i] - k。

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0; // 记录符合条件的子数组数量
        int pre = 0;   // 累加前缀和
        // HashMap 存储 (前缀和，该前缀和出现的次数)
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 初始化：前缀和为 0 出现了 1 次（处理从索引 0 开始的子数组）

        for (int num : nums) {
            pre += num; // 计算当前前缀和
            // 如果存在 pre - k，说明从那个位置到当前位置的子数组和正好为 k
            if (map.containsKey(pre - k)) {
                count += map.get(pre - k); // 累加次数
            }
            // 将当前前缀和存入或更新 map
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}

2. 题目二：滑动窗口最大值 (LeetCode 239)

题目背景

这是固定窗口的极致优化版。普通遍历是 O(n*k)，通过单调队列可以优化到 O(n)。