跳到主要内容

滑动窗口

滑动窗口通常用于处理一个长度可变的区间，通过定义 left 和 right 两个边界，动态调整窗口大小来满足条件。

209. 长度最小的子数组 (Minimum Size Subarray Sum)​

题目描述​

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解题思路​

右边界移动 + 结果更新 + 左边界收缩。

  1. 将 right 指针向右移动，把元素加进 sum。
  2. 一旦 sum >= target，说明满足条件。此时尝试收缩 left：
    • 记录当前长度 minLen = min(minLen, right - left + 1)。
    • sum -= nums[left++]。
    • 重复判断 sum >= target。

Java 代码实现​

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, res = Integer.MAX_VALUE, sum = 0, left = 0;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(res, right - left + 1);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

3. 无重复字符的最长子串 (Longest Substring Without Repeating Characters)​

题目描述​

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路​

哈希表记录下标。

  1. 使用 Map<Character, Integer> 记录每个字符及其出现的最新位置。
  2. right 指针向右跑。
  3. 如果 map 中已存在 s.charAt(right)，说明有重复。将 left 移动到该重复字符上一次出现位置的下一格：left = max(left, map.get(c) + 1)。
  4. 更新 map 和 maxLen。

Java 代码实现​

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

30. 串联所有单词的子串 (Substring with Concatenation of All Words)​

题目描述​

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

解题思路​

外层步长遍历 + 内部哈希统计。

  1. 设单词长度为 wLen，由于起始位置可能是从 0 到 wLen-1 开始的。
  2. 对每一个可能的初始位置做一次完整的滑动窗口。
  3. 维护 diff（当前窗口内单词频次与 words 的差异）。

Java 代码实现​

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int n = s.length(), m = words.length, len = words[0].length();
        Map<String, Integer> counts = new HashMap<>();
        for (String w : words) counts.put(w, counts.getOrDefault(w, 0) + 1);
        for (int i = 0; i < len; i++) {
            Map<String, Integer> window = new HashMap<>();
            int count = 0, left = i;
            for (int right = i; right <= n - len; right += len) {
                String word = s.substring(right, right + len);
                if (counts.containsKey(word)) {
                    window.put(word, window.getOrDefault(word, 0) + 1);
                    count++;
                    while (window.get(word) > counts.get(word)) {
                        String leftWord = s.substring(left, left + len);
                        window.put(leftWord, window.get(leftWord) - 1);
                        count--;
                        left += len;
                    }
                    if (count == m) res.add(left);
                } else {
                    window.clear();
                    count = 0;
                    left = right + len;
                }
            }
        }
        return res;
    }
}

76. 最小覆盖子串 (Minimum Window Substring)​

题目描述​

给你一个字符串 s 、一个字符串 t 。返回 s 中包含 t 所有字符的最小子串。如果 s 中不存在符合条件的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

解题思路​

统计 + 计数器 + 滑动收缩。

  1. 使用 need 哈希表存储 t 中每个字符出现的频次，window 哈希表存储当前窗口内各字符的频次。
  2. 用 valid 变量记录窗口中满足 need 条件的字符数。
  3. right 一直移动，当 valid == need.size() 表示找齐了，记录结果。
  4. 尝试收缩 left：减小 window 里的计数，直到不满足找齐条件为止。

Java 代码实现​

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
        int left = 0, right = 0, valid = 0, start = 0, minLen = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++;
            }
            while (valid == need.size()) {
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}