 字符串哈希)
- 教程
- 文档
【免费下载链接】LogicStack-LeetCode
公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码
本篇技术指南以 LogicStack-LeetCode 仓库中的 LeetCode/181-190/187. 重复的DNA序列（中等）.md 为骨架，系统讲解 LeetCode 第 187 题「重复的 DNA 序列」的两种经典解法：滑动窗口 + 哈希表计数，以及字符串哈希 + 前缀和的严格 O(n) 优化方案。读完本文，你将掌握定长子串统计类问题的常规做法与哈希优化套路，理解为何计数容器的 key 类型会直接影响复杂度，并学会处理字符串哈希溢出与进制参数选择的实战经验。
题目背景与约束分析
所有 DNA 都由一系列缩写为'A'、'C'、'G'和'T'的核苷酸组成，例如"ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
题目要求：编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串s中出现次数超过一次。
示例 1： 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：["AAAAACCCCC","CCCCCAAAAA"] 示例 2： 输入：s = "AAAAAAAAAAAAA" 输出：["AAAAAAAAAA"]约束条件：
0 <= s.length <= 10^5s[i]为'A'、'C'、'G'或'T'
从约束可以看出：字符串长度可达 10 万，而目标子串长度固定为 10，因此最多只有约10^5个长度为 10 的子串需要检查。数据范围决定了"朴素枚举 + 哈希统计"在该题下是可行的，但若把子串长度放大到 100 以上，就必须考虑更高效的方案——这正是本文两个解法分层递进的意义所在。
解法一：滑动窗口 + 哈希表计数
核心思路
数据范围只有10^5，一个朴素且直接的想法是：从左到右处理字符串s，使用滑动窗口得到每个以s[i]为结尾（或起点）且长度为 10 的子串，同时使用哈希表记录每个子串的出现次数；如果某个子串的出现次数超过一次，就将其加入答案。
这里有一个值得注意的去重细节：为了防止相同的子串被重复添加到答案，而又不想使用常数较大的Set结构，可以规定——当且仅当该子串在之前出现过一次（加上本次，当前出现次数恰好为两次）时，才将子串加入答案。这样每个重复子串只会在计数从 1 变成 2 的那一次被加入答案，天然完成去重。
完整代码（Java）
class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> ans = new ArrayList<>(); int n = s.length(); Map<String, Integer> map = new HashMap<>(); for (int i = 0; i + 10 <= n; i++) { String cur = s.substring(i, i + 10); int cnt = map.getOrDefault(cur, 0); if (cnt == 1) ans.add(cur); map.put(cur, cnt + 1); } return ans; } }复杂度分析
- 时间复杂度：
O(n * C)。每次检查一个以s[i]为起点的子串，都需要通过substring构造出新的、长度为 10 的字符串，令C = 10，总复杂度为O(n * C)。 - 空间复杂度：
O(n)。长度固定的子串数量不会超过n个，哈希表最多存储n个键值对。
解法一的局限
子串长度为 10，因此上述解法的计算量约为10^6，在 LeetCode 的时限内可以通过。但如果题目给定的子串长度大于 100，加上生成子串和哈希表本身的常数操作，计算量将超过10^7，此时会 TLE。这说明"窗口滑动 + 字符串计数"的做法其复杂度与子串长度线性相关，无法应对更长的子串查询需求。
解法二：字符串哈希 + 前缀和（严格 O(n)）
核心思路
一个能够做到严格 O(n)的做法是使用「字符串哈希 + 前缀和」，这也是本文档的核心技术点。
具体做法是：使用一个与字符串s等长的哈希数组h[]，以及次方数组p[]：
h[i]表示字符串前i个字符（即前缀s[0..i-1]）的哈希值；p[i]表示进制P的i次方，即P^i。
由字符串预处理得到这样的哈希数组和次方数组，复杂度为O(n)。当需要计算子串s[i..j]的哈希值时，只需要利用前缀和思想：
hash(s[i..j]) = h[j] - h[i - 1] * p[j - i + 1]即可在O(1)时间内得出哈希值，与子串长度无关。这与普通的前缀和求区间和（sum[j] - sum[i-1]）在思想上一脉相承——先预处理全局前缀信息，再用减法快速得到任意区间的聚合值；仓库的 Index/前缀和.md 中收录了 53、304、560 等大量同思想题目，可作为横向参考。
关键细节：计数哈希表的 key 类型
如果期望做到严格 O(n)，进行计数的哈希表就不能以String作为 key，只能使用Integer（也就是 hash 结果本身）作为 key。
原因在于：Java 中String的hashCode实现会遍历字符串的每个字符来计算散列值，这样哈希计数过程的时间仍与子串长度有关；而Integer的hashCode就是该值本身（返回 int 原值），这是与长度无关的 O(1) 操作。只有把"求子串哈希"和"哈希表统计"两部分的长度依赖都消掉，才能达到真正的严格 O(n)。
完整代码（Java）
class Solution { int N = (int)1e5+10, P = 131313; int[] h = new int[N], p = new int[N]; public List<String> findRepeatedDnaSequences(String s) { int n = s.length(); List<String> ans = new ArrayList<>(); p[0] = 1; for (int i = 1; i <= n; i++) { h[i] = h[i - 1] * P + s.charAt(i - 1); p[i] = p[i - 1] * P; } Map<Integer, Integer> map = new HashMap<>(); for (int i = 1; i + 10 - 1 <= n; i++) { int j = i + 10 - 1; int hash = h[j] - h[i - 1] * p[j - i + 1]; int cnt = map.getOrDefault(hash, 0); if (cnt == 1) ans.add(s.substring(i - 1, i + 10 - 1)); map.put(hash, cnt + 1); } return ans; } }代码采用 1-based 下标：h[i]对应字符串前i个字符，p[i]对应P^i。预处理循环中h[i] = h[i-1] * P + s.charAt(i-1)是字符串哈希的标准递推式；查询循环中枚举每个长度为 10 的子串起点i，终点j = i + 9，用h[j] - h[i-1] * p[j-i+1]得到该子串的哈希值，再走一遍"计数恰为 1 时加入答案"的去重逻辑，最后通过substring(i-1, i+10-1)还原真实字符串。
复杂度分析
- 时间复杂度：
O(n)。预处理哈希数组与次方数组为O(n)，滑动枚举与 O(1) 哈希查询同样为O(n)，整体严格线性。 - 空间复杂度：
O(n)。需要两个长度为n的辅助数组，以及存储哈希计数的哈希表。
实战经验：溢出与进制参数选择
这是本文档中极有价值的实战问答部分，直接关系到字符串哈希方案的工程可用性。
问题一：构造 p 数组和计算哈希的过程会溢出吗？
会溢出，溢出就会变为负数。当且仅当两个哈希值溢出程度与Integer.MAX_VALUE呈不同的倍数关系时，会产生错误结果（即哈希冲突）。此时可以考虑修改进制P，或者采用表示范围更大的long来代替int。
值得补充的是，仓库中同系列的其他题目给出了不同场景下的选择：例如 1044. 最长重复子串（困难） 的字符串哈希 + 二分解法中，作者直接使用long[] h, p与更大的进制P = 1313131来进一步降低冲突概率，这说明进制与容器类型的选择应结合数据规模（n 的大小）和哈希表判重的严谨程度来权衡。
问题二：P = 131313 这个数字是怎么来的？
是"WA 出来的"：作者刚开始使用P = 131，被卡在了 30/31 个样例上。字符串哈希本身存在哈希冲突的可能，一般会在尝试131之后尝试使用13131，然后再尝试使用比13131更大的质数。
这条经验揭示了一个工程事实：字符串哈希是"概率正确"的方案，在极限测试数据下可能因冲突而 WA。选择更大的质数进制、使用更宽的整数类型（long而非int）、必要时配合二次哈希（双进制双哈希）验证，都是降低冲突风险的标准手段。在 686. 重复叠加字符串匹配（中等） 中，同样的字符串哈希模板被用于子串匹配场景，可见这套预处理 + O(1) 查询的框架在仓库的"字符串哈希"主题下具备通用复用价值，相关题目索引见 Index/字符串哈希.md。
两种解法对比与选型建议
| 维度 | 滑动窗口 + 哈希表 | 字符串哈希 + 前缀和 |
|---|---|---|
| 计数 key | String（长度相关） | Integer（长度无关） |
| 子串哈希计算 | 每次substring构造，O(C) | 前缀和公式 O(1) |
| 时间复杂度 | O(n * C) | O(n) |
| 空间复杂度 | O(n) | O(n) |
| 适用场景 | 子串长度 C 很小（如本题 C=10） | 子串长度较大或需频繁查询任意区间 |
实际选题时：若子串长度固定且很小（如本题的 10），两种做法都能通过，解法一更直观易写；若子串长度达到 100 以上、或者需要在一个长串上反复查询不同长度的子串，则应采用解法二，因为它的查询成本与长度完全解耦。若对正确性要求极高、担心哈希冲突，可采用long型哈希并配合更大质数进制，正如 1044 题所演示的那样。
延伸阅读：仓库中的相关资源
- Index/字符串哈希.md：字符串哈希主题的完整题目索引，含 187、472、686、1044、1668 等题；
- Index/滑动窗口.md 与 Index/前缀和.md：本题涉及的两种基础思想在仓库中的归类入口；
- LeetCode/1041-1050/1044. 最长重复子串（困难）.md：字符串哈希 + 二分的进阶应用，展示
long哈希与更大进制的写法； - LeetCode/681-690/686. 重复叠加字符串匹配（中等）.md：同一字符串哈希模板用于子串匹配（含 KMP 对照实现）。
本题作为「刷穿 LeetCode」系列的第 No.187 篇，完整题解与代码统一收录于本仓库（LogicStack-LeetCode），读者可通过git clone https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode获取全量文档后进行本地查阅与调试。
- 教程
- 文档
【免费下载链接】LogicStack-LeetCode
公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码
相关推荐
位编码滚动哈希与滑动窗口：LeetCode-Go 中第 187 题“重复的 DNA 序列”两种解法精讲
位编码滚动哈希与滑动窗口：LeetCode Go 中第 187 题“重复的 DNA 序列”两种解法精讲 本篇围绕 LeetCode 第 187 题 Repeat
示例工程LeetCode-Go 题解 187：Repeated DNA Sequences —— 用位运算滑动哈希精准定位重复 DNA 序列
LeetCode Go 题解 187：Repeated DNA Sequences —— 用位运算滑动哈希精准定位重复 DNA 序列 导读 本篇基于 LeetC
示例工程字符串哈希全解：从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战（LogicStack-LeetCode 刷穿系列）
字符串哈希全解：从滚动哈希原理到 LeetCode 重复子串/连接词/字符串轮转实战（LogicStack LeetCode 刷穿系列） 字符串哈希（Strin
教程文档
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
