字符计数窗口：哈希表与滑动窗口的黄金组合

摘要

字符串是滑动窗口最常见的应用场景，而字符频率计数是字符串窗口的核心维护技术。本文以三道题递进展开：LeetCode 438（找字符串中所有字母异位词，固定窗口+字符计数）、LeetCode 30（与所有单词相关联的子串，固定窗口+单词计数，将”字符”升级为”单词”）、LeetCode 187（重复的 DNA 序列，固定窗口+哈希去重）。通过这三题，系统讲解字符计数窗口的核心技巧：频率数组与 HashMap 的选型、“match 计数器”的高效匹配逻辑、以及将固定窗口应用于”多词串联”时的设计挑战。

第 1 章字符计数的本质：将字符串问题转化为频率向量问题

1.1 字符串比较的低效性

两个字符串直接比较（s1.equals(s2)）是 $O (n)$ 的。在固定窗口滑动时，如果每次移动都做字符串比较，总复杂度是 $O (n \cdot k)$ （ $n$ 次移动，每次 $O (k)$ 的比较），退化到接近 $O (n^{2})$ 。

字符频率计数的核心思想是：用字符频率向量替代字符串本身。两个字符串是否互为字母异位词，等价于它们的频率向量是否相等。频率向量的比较是 $O (∣Σ∣)$ 的（字符集大小），对于固定字符集（如 26 个字母），这是 $O (1)$ 。

1.2 频率数组 vs HashMap：深入对比

前文已初步介绍，这里做更系统的比较：

频率数组 int[26] / int[128]

优点：

访问速度极快（直接数组索引，缓存友好）
无装箱/拆箱开销
比较两个频率数组可以用 Arrays.equals(a, b)， $O (26) = O (1)$
代码简洁

缺点：

只适用于固定字符集（26 字母、ASCII 等）
当字符集稀疏时（如 LeetCode 30 的单词，频率数组不适用）

HashMap<Character, Integer>

优点：

适用于任意字符集
自动处理稀疏情况（只存储出现过的字符）

缺点：

装箱/拆箱开销（char → Character，int → Integer）
哈希冲突的小概率风险
代码稍繁琐（需要 getOrDefault 等）

选型规则：题目说”只包含小写字母”→ 用 int[26]；说”只包含英文字母”→ 用 int[52] 或 int[128]；元素是单词/整数/任意对象 → 用 HashMap。

1.3 match 计数器：避免全量数组比较

第 02 篇已介绍了 match 计数器的思路，这里系统化：

维护 int match，表示”当前窗口中满足需求的字符种类数”。

某字符 c 的窗口频率从 need[c]-1 增加到 need[c] 时（进窗时），match++
某字符 c 的窗口频率从 need[c] 减少到 need[c]-1 时（出窗时），match--
当 match == distinct（need 中不同字符的种类数）时，窗口与 need 完全匹配

这样判断是否匹配只需检查 match == distinct， $O (1)$ ，而不需要 $O (26)$ 的 Arrays.equals。

第 2 章 LeetCode 438：找字符串中所有字母异位词

2.1 题目

LeetCode 438 - Find All Anagrams in a String（中等）

给你两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引（顺序不限）。

字母异位词：相同字母不同顺序组成的字符串。

输入：s = "cbaebabacd", p = "abc"
输出：[0, 6]
解释：索引 0 处的子串 "cba" 是 "abc" 的字母异位词
      索引 6 处的子串 "bac" 是 "abc" 的字母异位词

输入：s = "abab", p = "ab"
输出：[0, 1, 2]

2.2 与 LeetCode 567 的对比

LeetCode 567（字符串的排列）和 LeetCode 438 本质完全相同：567 只问”是否存在”，438 问”所有起始位置”。

代码框架也几乎相同，只是”答案更新”从 return true 变成 result.add(left)：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int k = p.length();
    int n = s.length();
    if (k > n) return result;
 
    int[] need = new int[26];
    int[] window = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
 
    // 初始化第一个窗口
    for (int i = 0; i < k; i++) window[s.charAt(i) - 'a']++;
    if (Arrays.equals(window, need)) result.add(0);
 
    // 滑动
    for (int right = k; right < n; right++) {
        window[s.charAt(right) - 'a']++;           // 进窗
        window[s.charAt(right - k) - 'a']--;       // 出窗
        if (Arrays.equals(window, need)) result.add(right - k + 1);
    }
    return result;
}

2.3 用 match 计数器优化

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int k = p.length();
    int n = s.length();
    if (k > n) return result;
 
    int[] need = new int[26];
    for (char c : p.toCharArray()) need[c - 'a']++;
 
    // 计算 p 中有多少种不同字符
    int distinct = 0;
    for (int x : need) if (x > 0) distinct++;
 
    int[] window = new int[26];
    int match = 0;
 
    // 初始化
    for (int i = 0; i < k; i++) {
        int c = s.charAt(i) - 'a';
        window[c]++;
        if (need[c] > 0 && window[c] == need[c]) match++;
    }
    if (match == distinct) result.add(0);
 
    // 滑动
    for (int right = k; right < n; right++) {
        int inC = s.charAt(right) - 'a';
        int outC = s.charAt(right - k) - 'a';
 
        // 进窗
        window[inC]++;
        if (need[inC] > 0 && window[inC] == need[inC]) match++;
 
        // 出窗
        if (need[outC] > 0 && window[outC] == need[outC]) match--;
        window[outC]--;
 
        if (match == distinct) result.add(right - k + 1);
    }
    return result;
}

出窗时 match 更新的顺序：注意必须先检查 window[outC] == need[outC]（频率还在需求值时），再做 window[outC]--。如果顺序反了，减少后再检查，就错过了”恰好满足”→“不满足”的触发时机。

生产避坑：字符进出窗口时的 match 更新顺序

进窗时：先 window[c]++，再检查 window[c] == need[c]（从 need-1 变成 need 时 match++）出窗时：先检查 window[c] == need[c]（在 need 值时 match—），再 window[c]-- 顺序反了就会出现”频率已经变化了，但 match 没有正确更新”的 bug，非常难排查。

第 3 章 LeetCode 30：与所有单词相关联的子串

3.1 题目

LeetCode 30 - Substring with Concatenation of All Words（困难）

给定一个字符串 s 和一个字符串数组 words（所有单词等长，长度为 wordLen），找出 s 中恰好是 words 的某个全排列拼接而成的所有子串的起始位置。

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：起始索引 0 的子串 "barfoo" 是 words 的一个排列
      起始索引 9 的子串 "foobar" 是 words 的一个排列

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[8]

3.2 将字符级窗口升级为单词级窗口

这道题是 438 的”升级版”：把”字符”替换成”单词”，把”字符计数”升级为”单词计数”。

固定窗口大小：words.length * wordLen（所有单词拼接后的总长度）。

单词级计数：用 Map<String, Integer> need 记录每个单词需要出现的次数，用 Map<String, Integer> window 记录当前窗口内每个单词的频率。

挑战：不能简单地以字符为单位滑动，因为单词是等长的 wordLen 个字符的块。右指针每次跳 wordLen，而不是 1。

但如果右指针以 wordLen 为步长，窗口只覆盖了对齐到 0 的情况（从 0, wordLen, 2*wordLen… 开始的子串）。从 1, 2, …, wordLen-1 开始的子串也需要检查。

解决方案：以 offset = 0, 1, ..., wordLen-1 为起点，分别运行 wordLen 遍固定窗口扫描。

3.3 完整实现

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int n = s.length();
    int wordLen = words[0].length();
    int wordCount = words.length;
    int windowLen = wordLen * wordCount;
    if (n < windowLen) return result;
 
    // 统计需求频率
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);
 
    // 以 offset 为起点，步长 wordLen，运行固定窗口
    for (int offset = 0; offset < wordLen; offset++) {
        Map<String, Integer> window = new HashMap<>();
        int match = 0;  // 当前满足需求的单词种类数
        int distinctNeeded = need.size();
 
        // 初始化：填入第一个窗口（wordCount 个单词）
        int right = offset;
        for (int i = 0; i < wordCount && right + wordLen <= n; i++, right += wordLen) {
            String w = s.substring(right, right + wordLen);
            window.merge(w, 1, Integer::sum);
            if (need.containsKey(w) && window.get(w).equals(need.get(w))) match++;
        }
        // 检查第一个窗口
        if (right == offset + windowLen && match == distinctNeeded) {
            result.add(offset);
        }
 
        // 滑动：right 继续向右，left = right - windowLen 的位置出窗
        while (right + wordLen <= n) {
            // 进窗：右边加入一个新单词
            String inW = s.substring(right, right + wordLen);
            right += wordLen;
            if (need.containsKey(inW)) {
                window.merge(inW, 1, Integer::sum);
                if (window.get(inW).equals(need.get(inW))) match++;
                else if (window.get(inW) == need.get(inW) + 1) match--;  // 超额了
            } else {
                window.merge(inW, 1, Integer::sum);
                // 不在 need 中，不影响 match
            }
 
            // 出窗：左边移除最旧的单词（位置 right - windowLen - wordLen）
            String outW = s.substring(right - windowLen - wordLen, right - windowLen);
            if (need.containsKey(outW)) {
                if (window.get(outW).equals(need.get(outW))) match--;
                window.merge(outW, -1, Integer::sum);
                if (window.get(outW) == 0) window.remove(outW);
                // 重新检查是否恰好满足
                if (need.containsKey(outW) && window.containsKey(outW)
                    && window.get(outW).equals(need.get(outW))) match++;
            } else {
                window.merge(outW, -1, Integer::sum);
                if (window.get(outW) == 0) window.remove(outW);
            }
 
            // 检查当前窗口
            if (match == distinctNeeded) result.add(right - windowLen);
        }
    }
    return result;
}

上面的代码逻辑有些复杂，让我们整理一个更清晰的版本：

public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> result = new ArrayList<>();
    int n = s.length();
    int wLen = words[0].length();   // 每个单词的长度
    int wCount = words.length;      // 单词数量
    int winLen = wLen * wCount;     // 窗口总长度
    if (n < winLen) return result;
 
    Map<String, Integer> need = new HashMap<>();
    for (String w : words) need.merge(w, 1, Integer::sum);
 
    // offset = 0, 1, ..., wLen-1，分 wLen 轮
    for (int offset = 0; offset < wLen; offset++) {
        Map<String, Integer> window = new HashMap<>();
        int formed = 0;   // 窗口内频率 == need 中频率的单词种类数
        int left = offset; // 以单词为步长的左端点（字节位置）
 
        for (int right = offset; right + wLen <= n; right += wLen) {
            // 进窗
            String w = s.substring(right, right + wLen);
            window.merge(w, 1, Integer::sum);
            if (need.containsKey(w)) {
                int cnt = window.get(w), ncnt = need.get(w);
                if (cnt.equals(ncnt)) formed++;
                else if (cnt == ncnt + 1) formed--;  // 刚从恰好变成超额
            }
 
            // 当窗口内单词数超过 wCount 时，出窗
            if ((right - left) / wLen + 1 > wCount) {
                String out = s.substring(left, left + wLen);
                if (need.containsKey(out)) {
                    int cnt = window.get(out), ncnt = need.get(out);
                    if (cnt.equals(ncnt)) formed--;  // 即将从恰好变成不足
                    else if (cnt == ncnt + 1) formed++;  // 从超额变成恰好
                }
                window.merge(out, -1, Integer::sum);
                if (window.get(out) == 0) window.remove(out);
                left += wLen;
            }
 
            // 窗口大小 == wCount 时检查答案
            if ((right - left) / wLen + 1 == wCount && formed == need.size()) {
                result.add(left);
            }
        }
    }
    return result;
}

时间复杂度： $O (n \cdot w L e n)$ ，因为每个 offset 下扫描 $O (n / w L e n)$ 个单词，每次操作 $O (w L e n)$ （substring 构造），共 $w L e n$ 个 offset

空间复杂度： $O (wC o u n t \cdot w L e n)$ （HashMap 中存储当前窗口的单词）

3.4 LeetCode 30 的核心难点总结

难点	解决方案
不能以字符为单位滑动	以 `wLen` 为步长的固定窗口
不同起始位置（对齐问题）	循环 `offset = 0..wLen-1`，共 `wLen` 轮扫描
单词计数而非字符计数	用 `Map<String, Integer>` 替代 `int[]`
match 的精确维护	区分”恰好满足”、“不足”、“超额”三种状态

第 4 章 LeetCode 187：重复的 DNA 序列

4.1 题目

LeetCode 187 - Repeated DNA Sequences（中等）

DNA 序列由 ‘A’, ‘C’, ‘G’, ‘T’ 组成。给定一个代表 DNA 序列的字符串 s，返回所有在 DNA 分子中出现不止一次的长度为 10 的序列（子字符串）。

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

4.2 固定窗口 + 哈希去重

这道题不是求最长/最短，而是找出重复出现的固定长度子串。思路：用固定窗口枚举所有长度为 10 的子串，用 HashSet 记录已见过的子串，当某个子串第二次出现时加入结果集。

public List<String> findRepeatedDnaSequences(String s) {
    List<String> result = new ArrayList<>();
    if (s.length() <= 10) return result;
 
    Set<String> seen = new HashSet<>();
    Set<String> added = new HashSet<>();  // 防止同一子串加入多次
 
    for (int i = 0; i <= s.length() - 10; i++) {
        String sub = s.substring(i, i + 10);
        if (seen.contains(sub) && !added.contains(sub)) {
            result.add(sub);
            added.add(sub);
        }
        seen.add(sub);
    }
    return result;
}
// 时间复杂度：O(10n) = O(n)（每次 substring 创建长度 10 的字符串）
// 空间复杂度：O(10n) = O(n)（HashSet 存储子串）

4.3 优化：Rabin-Karp 滚动哈希

substring 每次创建新的字符串对象，虽然长度固定为 10，但大量字符串对象的创建和 GC 有开销。使用**滚动哈希（Rolling Hash）**可以避免显式创建子串：

思路：将每个字符编码为 2 bit（A=0, C=1, G=2, T=3），10 个字符编码为 20 bit 的整数。滚动时，去掉最高 2 bit（左移 2 位清零），加上新字符的 2 bit（右移到最低位），得到新的哈希值。

public List<String> findRepeatedDnaSequences(String s) {
    List<String> result = new ArrayList<>();
    int n = s.length();
    if (n <= 10) return result;
 
    // 字符编码：A=0, C=1, G=2, T=3
    Map<Character, Integer> code = Map.of('A', 0, 'C', 1, 'G', 2, 'T', 3);
 
    Set<Integer> seen = new HashSet<>();
    Set<Integer> added = new HashSet<>();
 
    int hash = 0;
    int mask = (1 << 20) - 1;  // 20 bit 的掩码（保留低 20 bit）
 
    // 初始化第一个窗口
    for (int i = 0; i < 10; i++) {
        hash = (hash << 2) | code.get(s.charAt(i));
    }
    seen.add(hash);
 
    // 滑动
    for (int right = 10; right < n; right++) {
        hash = ((hash << 2) | code.get(s.charAt(right))) & mask;  // 加入新字符，保留 20 bit
        if (seen.contains(hash) && !added.contains(hash)) {
            result.add(s.substring(right - 9, right + 1));
            added.add(hash);
        }
        seen.add(hash);
    }
    return result;
}

核心概念：Rabin-Karp 滚动哈希

滚动哈希是固定窗口中处理字符串的高效技术：用整数表示窗口内容，每次滑动时 $O (1)$ 计算新哈希（旧哈希移位 + 加入新字符 + 去掉旧字符）。与字符串对比相比，整数哈希比较是 $O (1)$ 且 GC 友好。

注意：滚动哈希存在哈希碰撞的理论风险，但对于 DNA 序列（4^10 = 100 万种可能），20 bit 整数（2^20 ≈ 100 万）恰好能覆盖，碰撞概率为 0。

时间复杂度： $O (n)$ （无字符串创建开销） 空间复杂度： $O (n)$ （HashSet 存储整数哈希）

4.4 为什么本题也是”固定窗口”

187 的结构：枚举所有长度为 10 的子串 → 这是固定窗口（ $k = 10$ ）。窗口状态是”子串内容”，用字符串哈希表示。“答案更新”是”当前子串已见过则加入结果”。与 643 的”最大和”、438 的”字母异位词”相比，本题的”答案更新逻辑”更复杂，但固定窗口的骨架完全相同。

第 5 章字符计数窗口的变体与局限

5.1 编码升级：从字符到 k-mer

LeetCode 187 的滚动哈希思路可以推广到任意”固定长度块”的计数。在基因组学中，长度为 $k$ 的子串叫 $k$ -mer，用滚动哈希统计 $k$ -mer 频率是实际工程中的常见操作。

如果字母表大小是 $∣Σ∣$ ， $k$ -mer 有 $∣Σ ∣^{k}$ 种，当 $k$ 较小（ $k \leq 10$ 对于 4 字母 DNA）时，可以用整数精确编码；当 $k$ 较大时，整数溢出，需要取模哈希（有碰撞风险）。

5.2 字符计数窗口的局限

字符计数窗口在以下场景会失效：

字符有权重：如果每个字符的”价值”不同，字符频率计数不能直接反映窗口代价，需要另设统计量。

顺序有意义：字母异位词只关心频率，不关心顺序；但如果”子串需要按某种顺序排列”，纯频率计数就不够了（见 LeetCode 30 的单词版，必须严格拼接顺序——但等长单词放宽了这个要求）。

字符动态变化：如果窗口内字符可以被替换（如 LeetCode 424），“目标频率”不是固定的，纯计数窗口退化为需要维护”替换次数”的特殊形态（见第 04 篇）。

本篇总结

本篇系统讲解了字符计数窗口的三种形态：

LeetCode 438（字母异位词）：固定窗口 + 字符频率数组，match 计数器优化匹配判断
LeetCode 30（多词串联）：固定窗口 + 单词频率 HashMap，多 offset 循环解决对齐问题
LeetCode 187（重复 DNA 序列）：固定窗口 + 哈希去重，滚动哈希避免字符串对象创建

字符计数窗口的设计公式：

字符集小（≤ 128）→ int[] 数组
元素是单词/整数/任意对象 → HashMap
匹配判断 → Arrays.equals（简单）或 match 计数器（高效）
字符串内容哈希 → 滚动哈希（Rabin-Karp）

参考与延伸

02 固定长度滑动窗口：模板推导与三题精讲 — match 计数器的首次引入
03 最小覆盖子串：可变窗口收缩条件的黄金法则 — 字符计数在可变窗口中的应用
07 单调队列优化滑动窗口：O(n) 求窗口极值的艺术 — 固定窗口的另一类维护挑战

课后练习

LeetCode 2156 - 查找给定哈希值的子串（困难）

给你一个字符串 s，哈希函数定义为 hash(s, p, m) = (val(s[0]) * p^(k-1) + ... + val(s[k-1])) % m，找出哈希值等于给定 hashValue 的长度为 k 的子串（保证唯一）。

提示：正向滚动哈希遇到取模后无法「减去」最左字符的问题。技巧是从右往左遍历（逆向滚动哈希），每次加入最左字符时乘以 p^(k-1)，然后取模。本篇 LeetCode 187 的滚动哈希是入门，此题是进阶挑战。

汀的知识碎片

文章导航

06 字符计数窗口：哈希表与滑动窗口的黄金组合

字符计数窗口：哈希表与滑动窗口的黄金组合

摘要

第 1 章字符计数的本质：将字符串问题转化为频率向量问题

1.1 字符串比较的低效性

1.2 频率数组 vs HashMap：深入对比

1.3 match 计数器：避免全量数组比较

第 2 章 LeetCode 438：找字符串中所有字母异位词

2.1 题目

2.2 与 LeetCode 567 的对比

2.3 用 match 计数器优化

第 3 章 LeetCode 30：与所有单词相关联的子串

3.1 题目

3.2 将字符级窗口升级为单词级窗口

3.3 完整实现

3.4 LeetCode 30 的核心难点总结

第 4 章 LeetCode 187：重复的 DNA 序列

4.1 题目

4.2 固定窗口 + 哈希去重

4.3 优化：Rabin-Karp 滚动哈希

4.4 为什么本题也是”固定窗口”

第 5 章字符计数窗口的变体与局限

5.1 编码升级：从字符到 k-mer

5.2 字符计数窗口的局限

本篇总结

参考与延伸

课后练习

On this page

Backlinks

汀的知识碎片

文章导航

06 字符计数窗口：哈希表与滑动窗口的黄金组合

字符计数窗口：哈希表与滑动窗口的黄金组合

摘要

第 1 章 字符计数的本质：将字符串问题转化为频率向量问题

1.1 字符串比较的低效性

1.2 频率数组 vs HashMap：深入对比

1.3 match 计数器：避免全量数组比较

第 2 章 LeetCode 438：找字符串中所有字母异位词

2.1 题目

2.2 与 LeetCode 567 的对比

2.3 用 match 计数器优化

第 3 章 LeetCode 30：与所有单词相关联的子串

3.1 题目

3.2 将字符级窗口升级为单词级窗口

3.3 完整实现

3.4 LeetCode 30 的核心难点总结

第 4 章 LeetCode 187：重复的 DNA 序列

4.1 题目

4.2 固定窗口 + 哈希去重

4.3 优化：Rabin-Karp 滚动哈希

4.4 为什么本题也是”固定窗口”

第 5 章 字符计数窗口的变体与局限

5.1 编码升级：从字符到 k-mer

5.2 字符计数窗口的局限

本篇总结

参考与延伸

课后练习

On this page

Backlinks

第 1 章字符计数的本质：将字符串问题转化为频率向量问题

第 5 章字符计数窗口的变体与局限