滑动窗口：解题框架与经典题

什么是滑动窗口？

滑动窗口是一种处理连续子数组/子字符串问题的高效技巧，用 left 和 right 两个指针定义窗口边界，避免暴力双重循环的 O(n²)，达到 O(n)。

核心框架：

int left = 0, right = 0;
while (right < n) {
    // 1. 扩大窗口（right 右移，加入新元素）
    window.add(s.charAt(right));
    right++;

    // 2. 收缩窗口（条件不满足时，left 右移，移除旧元素）
    while (window 需要收缩) {
        window.remove(s.charAt(left));
        left++;
    }
    
    // 3. 更新答案
    res = Math.max(res, right - left);
}

固定长度窗口

大小为 k 的子数组的平均值

double[] findAvgOfSubarrays(int[] arr, int k) {
    double[] result = new double[arr.length - k + 1];
    double windowSum = 0;
    for (int i = 0; i < arr.length; i++) {
        windowSum += arr[i];
        if (i >= k - 1) {
            result[i - k + 1] = windowSum / k;
            windowSum -= arr[i - k + 1];  // 移除左侧滑出的元素
        }
    }
    return result;
}

不定长窗口

无重复字符的最长子串（LeetCode 3）

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, res = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        count.merge(c, 1, Integer::sum);   // 加入窗口
        while (count.get(c) > 1) {         // 有重复，收缩左边
            count.merge(s.charAt(left), -1, Integer::sum);
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
}

长度最小的子数组（LeetCode 209，和 ≥ target）

int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, res = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {   // 满足条件后尽量收缩
            res = Math.min(res, right - left + 1);
            sum -= nums[left++];
        }
    }
    return res == Integer.MAX_VALUE ? 0 : res;
}

最多含 k 个不同字符的最长子串

int lengthOfLongestSubstringKDistinct(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    int left = 0, res = 0;
    for (int right = 0; right < s.length(); right++) {
        count.merge(s.charAt(right), 1, Integer::sum);
        while (count.size() > k) {
            char lc = s.charAt(left);
            count.merge(lc, -1, Integer::sum);
            if (count.get(lc) == 0) count.remove(lc);
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
}

需要记录两个窗口的题

找到字符串中所有字母异位词（LeetCode 438）

List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int[] need = new int[26], window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
    for (int right = 0; right < s.length(); right++) {
        window[s.charAt(right) - 'a']++;
        if (right >= p.length())
            window[s.charAt(right - p.length()) - 'a']--;  // 固定窗口，移除左元素
        if (Arrays.equals(window, need))
            res.add(right - p.length() + 1);
    }
    return res;
}

最小覆盖子串（LeetCode 76）

在 s 中找包含 t 所有字符的最小子串：

String minWindow(String s, String t) {
    int[] need = new int[128], have = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    int left = 0, formed = 0, required = t.length();
    int resLen = Integer.MAX_VALUE, resStart = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        have[c]++;
        if (need[c] > 0 && have[c] <= need[c]) formed++;  // 有效字符增加
        
        while (formed == required) {  // 已覆盖所有字符，尝试收缩
            if (right - left + 1 < resLen) {
                resLen = right - left + 1;
                resStart = left;
            }
            char lc = s.charAt(left);
            have[lc]--;
            if (need[lc] > 0 && have[lc] < need[lc]) formed--;
            left++;
        }
    }
    return resLen == Integer.MAX_VALUE ? "" : s.substring(resStart, resStart + resLen);
}

滑动窗口 vs 前缀和

何时无法用滑动窗口？ 若数组包含负数且目标是求子数组的和等于某个值，窗口没有单调性，此时应用前缀和 + 哈希表。