企业官网建设流程全解析

位编码滚动哈希与滑动窗口：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，难度为 Medium：

All 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 = 0xFFFFF（20 位全 1）剔除最左端字符，再并入新字符。

README 中的解题思路原文正是这两条：

• 这一题不用位运算比较好做，维护一个长度为 10 的字符串，在 map 中出现次数 > 1 就输出。
• 用位运算想做这一题，需要动态的维护长度为 10 的 hashkey，先计算开头长度为 9 的 hash，在往后面扫描的过程中，如果长度超过了 10，就移除 hash 开头的一个字符，加入后面一个字符。具体做法是先将 ATCG 变成 00，01，10，11 的编码，那么长度为 10，hashkey 就需要维护在 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 : i+10]) if cache[curr] == 1 { ans = append(ans, curr) } cache[curr]++ } return ans }

这个实现与 README 中“维护一个长度为 10 的字符串，在 map 中出现次数 > 1 就输出”的思路一一对应，执行步骤是：

1. 边界处理：len(s) < 10时直接返回空切片[]string{}，因为不存在长度 10 的子串；
2. 滑动窗口：i从 0 遍历到len(s)-10（闭区间），s[i:i+10]就是第i个长度为 10 的窗口子串；
3. 计数判断：cache[curr] == 1表示该子串第一次被记录、当前是第二次出现，正是“出现超过一次”的判定时刻，于是加入ans。这里有一个细节——只在== 1时输出，而不是>= 1，因此一个出现 3 次、4 次的序列也只会输出一次，天然完成了去重；
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 = cur<<2 | 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:i+1]) } } 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 位；
• & 0xFFFFF：0xFFFFF是 20 个 1（十六进制 5 个 F），与运算把超出 20 位的高位截掉——相当于“移除 hash 开头的一个字符”（README 原话），这正是滚动窗口的位运算表达；
• | charMap[s[i]]：把新字符编码并入最低 2 位。

3. 两阶段循环

先单独用前 9 个字符“预热”：

for i := 0; i < 9; i++ { cur = cur<<2 | charMap[s[i]] }

从i = 9开始进入主循环，第一次执行滚动公式后，cur恰好覆盖s[0:10]；之后每一步cur都精确表示窗口s[i-9 : i+1]，输出子串时直接取s[i-9:i+1]，无需额外记录窗口位置。

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:i+1]) }

计数只在1 → 2的跳变时向结果追加一次，之后一律钳制在 2。这样做有两个好处：一是与字符串解法一样保证重复序列只输出一次；二是map[uint32]int的 key 从 10 字符的字符串缩小为 4 字节整数，比较与哈希成本更低，这也是位运算解法“runtime beats 100%”（仓库宣传的整体性能定位）的微观基础之一。

另外注意，该函数在输入过短时返回nil（而非空切片），与解法二返回[]string{}的行为略有差异——对于“判空/JSON 序列化”等下游使用场景，两者语义等价但表现形式不同，测试中通过打印输出对比了两者的表现。

两种解法对照

两者共享同一套算法骨架：定长窗口 + 哈希表计数 + 仅在第二次出现时输出，差异只在 key 的表示方式上。

测试用例与本地验证

测试文件 遵循仓库统一的测试模板：para187/ans187两个结构体分别承载输入输出，Test_Problem187中内置了 2 组用例（见 Test_Problem187）：

qs := []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 -covermode=atomic -coverprofile=coverage.txt ./leetcode/...，一次性产出单一合法的覆盖率文件。

小结

• 本题的通用套路是：定长（10）滑动窗口 + 哈希表计数，在计数值从 1 变 2 的瞬间输出，即可同时满足“出现超过一次”和“结果不重复”两个要求；
• 字符串 key 写法正确性最直观；位编码写法利用 ATCG 只有 4 个字符的特性，以 2 bit/字符 的 20 位整数作 key，配合((cur<<2) & 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