重复的DNA序列 图解题解
这道题到底在问什么
- s
- AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT
- 输出
- ["AAAAACCCCC","CCCCCAAAAA"]
- 解释
- 这两个长度10的子串各出现了2次
最优解：一步一步想明白
- 3对每个长度10的子串，去和它后面的每个子串逐字符比，相同就算重复。起点对有 O(n²) 个、每次比对又要 O(10)，整体 O(n²) 还带常数，串一长就很慢。我们想要扫一遍就解决。
- 4与其两两比对，不如边滑边记账：每滑到一个新位置，就把当前长度10的子串在哈希表里计数 +1。哈希表天生能 O(1) 判断「这个子串以前见过没」。
- 5为什么是「恰好等于 2」而不是「≥2」? 因为出现第 3、第 4 次时它已经被收过了，只在第 2 次收就天然去重，答案里同一个子串永远只出现一次。下面用一个小例子 ATCGATCGTAT、窗口长 4 把整个过程演给你看。
- 6s = ATCGATCGTAT · 窗口长 4这是缩小版示例串 ATCGATCGTAT(格子下方是下标)。我们让一个长度 4 的窗口从最左开始，一格一格往右滑。下面会长出一张哈希表 seen{子串→次数}。真题只是把 4 换成 10。
- 7ATCG 出现 2 次 → 收它提前剧透：绿色高亮的 ATCG(下标0-3)在下标 4-7 处又出现了一次，是这个小例子里唯一重复的长 4 子串。看 seen 表怎么把它逮出来。
- 8当前子串 = ATCG窗口停在最左，盖住 下标0..3，读出子串 ATCG。seen 表还空着，没见过它。
- 9第一次见 ATCG把 ATCG 计数设为 1，seen 表新增一行「ATCG → 1」(绿色是刚写入的)。次数才 1，先不收。
- 10当前子串 = TCGA窗口向右滑一格到 下标1..4，读出 TCGA。这是个没见过的新子串。
- 11第一次见 TCGAseen 表多一行「TCGA → 1」。计数 1，继续滑。
- 12当前子串 = CGAT再滑一格到 下标2..5，子串 CGAT，又是新面孔。
- 13第一次见 CGAT新增「CGAT → 1」。窗口一路向右，表越攒越多。
- 14当前子串 = GATC滑到 下标3..6，子串 GATC。还是没见过。
- 15第一次见 GATC新增「GATC → 1」。前 4 个窗口都是「第一次见」，一个没收。下一格要变天了。
- 16当前子串 = ATCG窗口滑到 下标4..7，读出的子串又是 ATCG！seen 表里 ATCG 那行命中(蓝色)，开头下标0-3 的 ATCG 也点亮了——它要凑成第 2 次了。
- 17seen[ATCG]=2 → 收 ATCGseen[ATCG] 从 1 升到 2，恰好等于 2 的这一刻，把 ATCG 收进答案。两段 ATCG(下标0-3 和 4-7)一起高亮。这就是滑窗 + 哈希计数的全部魔法。
- 18当前子串 = TCGT继续滑到 下标5..8，子串 TCGT。注意它和 TCGA 只差最后一位，是个全新子串。
- 19第一次见 TCGT新增「TCGT → 1」。后面的子串都不会再重复了，但算法照样老老实实记完。
- 20当前子串 = CGTA滑到 下标6..9，子串 CGTA，新子串。
- 21第一次见 CGTA新增「CGTA → 1」。还剩最后一个窗口位置。
- 22当前子串 = GTAT最后一个位置 下标7..10，窗口右端正好顶到末尾。子串 GTAT，再滑就出界了。
- 23全部窗口扫完最后新增「GTAT → 1」，8 个窗口全部扫完。整张 seen 表里只有 ATCG 计数到了 2，所以答案就是 [ATCG]。
- 24ATCG @ 下标0-3 与 4-7回放：绿色的两段 ATCG 就是被逮住的重复子串。真题把窗口长 4 换成 10、串换成那 32 字母，过程一模一样，最后得到 AAAAACCCCC、CCCCCAAAAA 两个。
- 25哈希表把「这子串见过没」从 O(n) 查找降到 O(1)。窗口滑 n 步、每步 O(1)(子串长固定 10，截取是常数)，整体 O(n)。
- 28如果写 ≥2，一个出现 3 次的子串会在第 2、3 次各收一次，答案里就重复了。只在恰好等于 2 的那一刻收，等于「第一次发现它重复」时收，之后再多次也不再收——这就是免去额外去重的关键。
- 30i=8 越界:窗口[8,11] 出界如果上界写成 i < len，i=8 时窗口要盖下标 8..11，可下标 11 根本不存在(本串末尾是 10)，截出来是残缺子串。正确上界是 i ≤ len−4(真题 len−10)，到 i=7 就停。
⚠️ 容易写错的地方
✗ 错：循环跑到 i < len
✓ 对：跑到 i ≤ len − 10
最后一个完整长10窗口起点是 len−10，越界会截出短子串
✗ 错：用 ≥2 当收集条件
✓ 对：用 == 2
≥2 会让出现 3 次以上的子串被重复收入答案
✗ 错：出现一次就先放进答案再删
✓ 对：计数到2 时才放
多绕一圈还易漏删，计数法一步到位且天然去重
完整代码（Python / C++ / Java）
Python
class Solution:
def findRepeatedDnaSequences(self, s):
seen = {} # 子串 -> 出现次数
res = []
for i in range(len(s) - 9): # 窗口左端
sub = s[i:i + 10] # 当前长10子串
seen[sub] = seen.get(sub, 0) + 1
if seen[sub] == 2: # 恰好第2次才收
res.append(sub)
return resC++
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<string,int> seen; // 子串->次数
vector<string> res;
for (int i = 0; i + 10 <= (int)s.size(); i++) {
string sub = s.substr(i, 10);
if (++seen[sub] == 2) // 恰好第2次
res.push_back(sub);
}
return res;
}
};Java
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
Map<String,Integer> seen = new HashMap<>();
List<String> res = new ArrayList<>();
for (int i = 0; i + 10 <= s.length(); i++) {
String sub = s.substring(i, i + 10);
int c = seen.getOrDefault(sub, 0) + 1;
seen.put(sub, c);
if (c == 2) res.add(sub); // 恰好第2次
}
return res;
}
}复杂度
时间复杂度
O(n)
窗口滑 n 步，每步截长10子串 + 哈希查写均摊 O(1)(子串长固定)
空间复杂度
O(n)
哈希表最多存 n 个长10子串(每个占常数空间)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 重复的DNA序列 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
串非常长(几百万)时，存子串字符串会很费内存，怎么优化?+
因为只有 ACGT 四种字母，每个字母能用 2 位二进制编码,长10子串恰好 20 位,正好塞进一个 int。滑窗时用位运算 O(1) 更新这个整数指纹(Rabin-Karp 滚动哈希),哈希表存 int 而非 string,内存和比较都更省。
为什么用「计数 == 2」就能去重,而不用额外的 set?+
计数恰好跨过 2 的那一刻是「第一次确认它重复」,只在这一刻收,之后第3、4次计数继续涨但不再触发收集。等价于「第一次发现重复时记一笔」,天然不重复。
如果要求返回每个重复子串出现的次数呢?+
seen 哈希表本身就是「子串→次数」,扫描结束后遍历表,把次数 ≥2 的条目连同次数一起输出即可,无需改主循环。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 重复的DNA序列 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。