位编码滚动哈希与滑动窗口LeetCode-Go 中第 187 题“重复的 DNA 序列”两种解法精讲【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇围绕 LeetCode 第 187 题 Repeated DNA Sequences重复的 DNA 序列基于 leetcode/0187.Repeated-DNA-Sequences/README.md 中的题目描述与解题思路结合 仓库中的两种 Go 实现 逐行展开你会掌握“定长滑动窗口 哈希计数”的通用套路以及“ATCG 二进制编码 20 位滚动掩码”的位运算技巧并了解如何在仓库的测试框架下验证这两套解法。题目描述题目原文来自 README难度为 MediumAll DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: ACGAATTCCG. When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.题目大意所有 DNA 由一系列缩写为 A、C、G、T 的核苷酸组成例如 ACGAATTCCG。在研究 DNA 时识别其中的重复序列有时会对研究非常有帮助。请编写一个函数查找 DNA 分子中所有出现超过一次的 10 个字母长的序列子串。示例输入s AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT 输出[AAAAACCCCC, CCCCCAAAAA]问题的关键特征在于窗口长度是固定的 10而字母表只有 4 个字符。这一点决定了两种典型解法朴素做法维护一个长度为 10 的字符串作为 key 做哈希计数出现次数 1 就输出进阶做法用位运算动态维护长度为 10 的 hash key——先把 A、C、G、T 编码为 00、01、10、11每个字符占 2 bit长度 10 的序列刚好需要 20 bit滚动时通过mask 0xFFFFF20 位全 1剔除最左端字符再并入新字符。README 中的解题思路原文正是这两条这一题不用位运算比较好做维护一个长度为 10 的字符串在 map 中出现次数 1 就输出。用位运算想做这一题需要动态的维护长度为 10 的 hashkey先计算开头长度为 9 的 hash在往后面扫描的过程中如果长度超过了 10就移除 hash 开头的一个字符加入后面一个字符。具体做法是先将 ATCG 变成 00011011 的编码那么长度为 10hashkey 就需要维护在 20 位。mask 0xFFFFF 就是 20 位的。维护了 hashkey 以后根据这个 hashkey 进行去重和统计频次。下面对照仓库源码逐一拆解。解法一字符串滑动窗口哈希解法二对应源码 findRepeatedDnaSequences1// 解法二 func findRepeatedDnaSequences1(s string) []string { if len(s) 10 { return []string{} } ans, cache : make([]string, 0), make(map[string]int) for i : 0; i len(s)-10; i { curr : string(s[i : i10]) if cache[curr] 1 { ans append(ans, curr) } cache[curr] } return ans }这个实现与 README 中“维护一个长度为 10 的字符串在 map 中出现次数 1 就输出”的思路一一对应执行步骤是边界处理len(s) 10时直接返回空切片[]string{}因为不存在长度 10 的子串滑动窗口i从 0 遍历到len(s)-10闭区间s[i:i10]就是第i个长度为 10 的窗口子串计数判断cache[curr] 1表示该子串第一次被记录、当前是第二次出现正是“出现超过一次”的判定时刻于是加入ans。这里有一个细节——只在 1时输出而不是 1因此一个出现 3 次、4 次的序列也只会输出一次天然完成了去重计数递增cache[curr]在判断之后执行保证首次出现计数为 0时不会误输出。复杂度窗口数为n - 9每个窗口子串长 10时间复杂度为 O(10n)即线性cache最多存 n-9 个 key空间复杂度 O(10n)。实现直观、正确性容易保证是最稳妥的写法。解法二ATCG 位编码 20 位滚动哈希解法一对应源码 findRepeatedDnaSequences// 解法一 func findRepeatedDnaSequences(s string) []string { if len(s) 10 { return nil } charMap, mp, result : map[uint8]uint32{A: 0, C: 1, G: 2, T: 3}, make(map[uint32]int, 0), []string{} var cur uint32 for i : 0; i 9; i { // 前9位忽略 cur cur2 | charMap[s[i]] } for i : 9; i len(s); i { cur ((cur 2) 0xFFFFF) | charMap[s[i]] if mp[cur] 0 { mp[cur] 1 } else if mp[cur] 1 { // 2重复 mp[cur] 2 result append(result, s[i-9:i1]) } } return result }这一版把 README 中描述的位运算方案完整落地核心由三部分组成1. 字符编码表map[uint8]uint32{A: 0, C: 1, G: 2, T: 3}每个核苷酸映射为一个 2 bit 的数A→00、C→01、G→10、T→11因此 10 个字符的序列恰好占 20 bit用一个uint32就能容纳。由于 4 个字符与 4 个 2bit 编码是双射编码后的cur值与原始 10 字符子串一一对应作为哈希 key 不会误判——这不是取模近似哈希而是无损的定长编码。2. 滚动更新左移 2 位 20 位掩码cur ((cur 2) 0xFFFFF) | charMap[s[i]]cur 2为新字符腾出最低 2 位 0xFFFFF0xFFFFF是 20 个 1十六进制 5 个 F与运算把超出 20 位的高位截掉——相当于“移除 hash 开头的一个字符”README 原话这正是滚动窗口的位运算表达| charMap[s[i]]把新字符编码并入最低 2 位。3. 两阶段循环先单独用前 9 个字符“预热”for i : 0; i 9; i { cur cur2 | charMap[s[i]] }从i 9开始进入主循环第一次执行滚动公式后cur恰好覆盖s[0:10]之后每一步cur都精确表示窗口s[i-9 : i1]输出子串时直接取s[i-9:i1]无需额外记录窗口位置。4. 频次饱和计数0/1/2 三态if mp[cur] 0 { mp[cur] 1 } else if mp[cur] 1 { // 2重复 mp[cur] 2 result append(result, s[i-9:i1]) }计数只在1 → 2的跳变时向结果追加一次之后一律钳制在 2。这样做有两个好处一是与字符串解法一样保证重复序列只输出一次二是map[uint32]int的 key 从 10 字符的字符串缩小为 4 字节整数比较与哈希成本更低这也是位运算解法“runtime beats 100%”仓库宣传的整体性能定位的微观基础之一。另外注意该函数在输入过短时返回nil而非空切片与解法二返回[]string{}的行为略有差异——对于“判空/JSON 序列化”等下游使用场景两者语义等价但表现形式不同测试中通过打印输出对比了两者的表现。两种解法对照维度解法一位编码findRepeatedDnaSequences解法二字符串窗口findRepeatedDnaSequences1哈希 key20 bit 的uint32无损编码长度为 10 的string窗口滚动((cur2) 0xFFFFF) \| codeO(1)每次截取s[i:i10]O(10)频次策略0/1/2 三态饱和计数普通递增计数1时输出过短输入返回nil[]string{}适用场景对常数因子敏感、追求极致性能逻辑直白最易维护两者共享同一套算法骨架定长窗口 哈希表计数 仅在第二次出现时输出差异只在 key 的表示方式上。测试用例与本地验证测试文件 遵循仓库统一的测试模板para187/ans187两个结构体分别承载输入输出Test_Problem187中内置了 2 组用例见 Test_Problem187qs : []question187{ { para187{AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT}, ans187{[]string{AAAAACCCCC, CCCCCAAAAA}}, }, { para187{AAAAA}, ans187{[]string{}}, }, }第一组即题目官方示例覆盖“两个不同序列各重复出现”的正常路径第二组AAAAA长度不足 10验证短输入的边界分支。用例循环里会同时调用findRepeatedDnaSequences其结果打印输出与findRepeatedDnaSequences1保证两套实现在同一组输入下都被执行覆盖——这与仓库整体 100% 测试覆盖率的工程要求一致。本地运行方式在仓库根目录需 Go 1.19见 go.mod# 仅运行第 187 题 go test -run Test_Problem187 -v ./leetcode/0187.Repeated-DNA-Sequences/ # 按仓库自带脚本跑全量覆盖率生成 coverage.txt bash gotest.sh其中 gotest.sh 的实现是go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...一次性产出单一合法的覆盖率文件。小结本题的通用套路是定长10滑动窗口 哈希表计数在计数值从 1 变 2 的瞬间输出即可同时满足“出现超过一次”和“结果不重复”两个要求字符串 key 写法正确性最直观位编码写法利用 ATCG 只有 4 个字符的特性以 2 bit/字符 的 20 位整数作 key配合((cur2) 0xFFFFF) | code完成 O(1) 滚动是“位运算替代字符串哈希”的典型范例仓库中两套解法共存并共享测试入口187. Repeated DNA Sequences.go、187. Repeated DNA Sequences_test.go可以直接作为“同一题目的多解法对照阅读”的样例第 187 题在根 README 的题目总表中标注为 Medium、对应本目录可顺带参考仓库内其他哈希/位运算题目的写法如 0136、0371 等位运算题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考