LeetCode 187. 重复的DNA序列
目录
题目描述
题意分析
给一个只由
A、C、G、T四种字符组成的字符串，要求找出其中所有长度恰好为 10、且在原串中出现次数不止一次的连续子串。有两个约定必须先厘清。第一，子串是连续的，且长度固定为 10，所以候选总数只有 $n - 9$ 个，不存在组合爆炸。第二，答案里每个符合条件的子串只列一次，哪怕它出现了五次；返回顺序不作要求。
约束信号：字符串长度上限 $10^5$，字符集只有 4 个。长度上限说明 $O(n)$ 或 $O(n \log n)$ 都能过，而两两比较所有窗口的 $O(n^2)$ 会有 $10^{10}$ 次字符比较，明显超时。字符集只有 4 个则暗示每个字符可以只用 2 个二进制位编码，10 个字符正好压进一个 20 位整数——这是本题的进阶优化方向。
边界情况：字符串长度小于 10 时一个候选窗口都没有，应返回空列表；全部字符相同（如 20 个
A）时，唯一的答案是那 10 个A组成的串，且只能出现一次。
解法：固定窗口 + 2 位滚动编码
核心思路
窗口长度固定为 10，真正需要解决的是两件事：如何 $O(1)$ 地得到下一个窗口的标识，以及如何让同一个重复片段只进答案一次。
DNA 只有
A/C/G/T四种字符，可分别编码为00/01/10/11。10 个字符恰好占 20 位，所以一个窗口可表示为基数为 4 的整数：$x = \sum_{j=0}^{9} code(s_{i+j}) \cdot 4^{9-j}$。窗口右移一格时，将旧编码左移 2 位、补入新字符，再用低 20 位掩码丢掉离开窗口的字符：code = ((code << 2) | value) & ((1 << 20) - 1)。这里常被叫做「滚动哈希」，但它不存在普通模哈希的碰撞。原因是：长度为 10 的 DNA 序列恰有 $4^{10} = 2^{20}$ 种，20 位整数也恰有 $2^{20}$ 种取值；而固定长度的四进制表示是唯一的，因此这是一一对应的完美编码。掩码只是删掉第 11 个及更早字符的高位，不会让两个不同的 10 字符窗口变成同一个值。若换成「多项式 + 取模」的通用滚动哈希，则必须用原串复核或双哈希处理碰撞，不能直接当作唯一标识。
用长度为 $2^{20}$ 的计数数组记录每个编码的出现次数。当计数从 1 变为 2 时加入答案；第 3 次以后不再加，于是无需第二个去重集合。
不变量：处理完下标 $i$ 后，当 $i \ge 9$ 时，
code精确表示子串s[i-9..i]；更新计数前，count[code]等于该窗口在之前结束的窗口中出现的次数。因此计数变为 2 恰好意味着第二次出现，既不会收录只出现一次的窗口，也不会重复收录。
解题步骤
- 定义窗口长度
WINDOW = 10和低 20 位掩码MASK = (1 << 20) - 1，并创建 $2^{20}$ 长的计数数组。- 从左到右扫描字符。每次先把
A/C/G/T映射为0/1/2/3，再通过「左移、补入、保留低 20 位」更新编码。- 前 9 个字符还凑不成完整窗口，只累积编码，不查计数。从 $i = 9$ 开始，
code才代表一个合法的长度 10 窗口。- 将
count[code]加一。若新计数恰好为 2，截取s[i-9, i+1)加入答案；若是 1，说明尚未重复；若大于 2，说明已经收录过。- 扫描结束后返回答案。
以
"AAAAAAAAAAA"走查关键边界：前 10 个A编码为 0，计数从 0 变为 1，不收录。读入第 11 个A后，左移会把最早的A推向窗口外，掩码保留低 20 位，新窗口编码仍为 0。计数变为 2，所以"AAAAAAAAAA"被加入一次。即使后面还有更多A，计数也只会变为 3、4……，不再触发== 2。正确性：由滚动不变量，每个合法窗口都被唯一编码并且恰好统计一次。某序列被收录当且仅当它的计数首次到达 2，因此答案中的每个序列都至少出现两次，所有出现至少两次的序列也都会被收录，且每个只收录一次。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
private static final int WINDOW = 10;
private static final int MASK = (1 << (WINDOW * 2)) - 1;
public List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<>();
int[] count = new int[1 << (WINDOW * 2)];
int code = 0;
for (int i = 0; i < s.length(); i++) {
code = ((code << 2) | encode(s.charAt(i))) & MASK;
if (i >= WINDOW - 1 && ++count[code] == 2) {
res.add(s.substring(i - WINDOW + 1, i + 1));
}
}
return res;
}
private int encode(char nucleotide) {
return switch (nucleotide) {
case 'A' -> 0;
case 'C' -> 1;
case 'G' -> 2;
default -> 3; // 题目保证剩余字符只会是 'T'。
};
}
}
func findRepeatedDnaSequences(s string) []string {
const window = 10
const mask = 1<<(window*2) - 1
count := make([]int, 1<<(window*2))
res := make([]string, 0)
code := 0
for i := 0; i < len(s); i++ {
code = (code<<2 | encodeNucleotide(s[i])) & mask
if i >= window-1 {
count[code]++
if count[code] == 2 {
res = append(res, s[i-window+1:i+1])
}
}
}
return res
}
func encodeNucleotide(nucleotide byte) int {
switch nucleotide {
case 'A':
return 0
case 'C':
return 1
case 'G':
return 2
default: // 题目保证剩余字符只会是 'T'。
return 3
}
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符只参与一次移位、或运算和计数；只在某个编码第二次出现时截取一个长度固定为 10 的结果串，不改变线性结论。
- 空间复杂度：辅助空间是 $O(4^{10}) = O(1)$，计数数组固定为 $2^{20}$ 个整数，不随 $n$ 增长。若把窗口长度推广为变量 $L$，则数组空间是 $O(4^L)$；返回结果占 $O(k)$ 不计入辅助空间。
关键点总结
- 先利用「字符集只有 4 种」做 2 位编码，再利用「窗口长度固定」做滚动更新，是本题从普通哈希表解法进一步优化的两个约束信号。
- 20 位编码是固定长度四进制数的唯一表示，不是「大概不冲突」的模哈希。面试时要能明确区分「无碰撞编码」与「需要复核的概率哈希」。
MASK = (1 << 20) - 1的作用是保留最近 10 个字符的 20 位，从而在左移时自动移除最早字符。- 计数变为 2 时才收录，同时完成「确实重复」和「答案去重」，比分别维护
seen与added两个集合更直接。- 只有完整窗口才能记数。用
i >= WINDOW - 1分隔「预热编码」与「处理窗口」，长度小于 10 的输入会自然返回空答案。
易错点总结
- 忘记保留低 20 位：编码会混入窗口之前的字符。例如同一个 10 字符片段出现在不同前缀之后时，会得到不同整数，从而漏掉重复。
- 直接用
nucleotide - 'A'编码：T - A = 19，早已超出 2 位范围，不同窗口可能串位。四个字符必须显式映射到 0、1、2、3。- 窗口未满 10 就计数：
"A"、"AA"等短前缀都会与高位补 0 的 10 字符窗口共用编码；必须在 $i \ge 9$ 后才更新次数。- 用
count[code] >= 2收录：同一片段第 3、4 次出现仍会追加答案。例如 12 个A有 3 个相同窗口，答案却只能包含一个"AAAAAAAAAA"，判断必须是== 2。- 把编码当成普通模哈希而多做碰撞复核：本题的 20 位表示本身就是无碰撞编码，再保存所有字符串复核只会增加存储和比较开销。但如果改成小模数的通用滚动哈希，则反过来必须处理碰撞。
- 截取边界少写或多写 1：以结束下标 $i$ 表示当前窗口时，左端是 $i - 9$，而 Java/Go 的右端为开区间 $i + 1$，因此应取
[i-9, i+1)。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 219. 存在重复元素 II | 简单 | 重复判定还附带下标距离约束 |
| 28. 找出字符串中第一个匹配项的下标 | 简单 | 定长模式串匹配，可用滚动哈希或前缀函数 |
| 438. 找到字符串中所有字母异位词 | 中等 | 定长窗口比较的是字符计数而非子串本身 |
| 1044. 最长重复子串 | 困难 | 长度不固定，需二分长度并配合滚动哈希 |