重复的DNA序列

对每个长度10的子串，去和它后面的每个子串逐字符比，相同就算重复。起点对有 O(n²) 个、每次比对又要 O(10)，整体 O(n²) 还带常数，串一长就很慢。我们想要扫一遍就解决。

与其两两比对，不如边滑边记账：每滑到一个新位置，就把当前长度10的子串在哈希表里计数 +1。哈希表天生能 O(1) 判断「这个子串以前见过没」。

为什么是「恰好等于 2」而不是「≥2」? 因为出现第 3、第 4 次时它已经被收过了，只在第 2 次收就天然去重，答案里同一个子串永远只出现一次。下面用一个小例子 ATCGATCGTAT、窗口长 4 把整个过程演给你看。

换个小例子看清滑窗：这是缩小版示例串 ATCGATCGTAT(格子下方是下标)。我们让一个长度 4 的窗口从最左开始，一格一格往右滑。下面会长出一张哈希表 seen{子串→次数}。真题只是把 4 换成 10。

目标先剧透：提前剧透：绿色高亮的 ATCG(下标0-3)在下标 4-7 处又出现了一次，是这个小例子里唯一重复的长 4 子串。看 seen 表怎么把它逮出来。

i=0 · 窗口[0,3] 读子串：窗口停在最左，盖住 下标0..3，读出子串 ATCG。seen 表还空着，没见过它。

i=0 · 记账 seen[ATCG]=1：把 ATCG 计数设为 1，seen 表新增一行「ATCG → 1」(绿色是刚写入的)。次数才 1，先不收。

i=1 · 窗口右滑[1,4]：窗口向右滑一格到 下标1..4，读出 TCGA。这是个没见过的新子串。

i=1 · 记账 seen[TCGA]=1：seen 表多一行「TCGA → 1」。计数 1，继续滑。

i=2 · 窗口右滑[2,5]：再滑一格到 下标2..5，子串 CGAT，又是新面孔。

i=2 · 记账 seen[CGAT]=1：新增「CGAT → 1」。窗口一路向右，表越攒越多。

i=3 · 窗口右滑[3,6]：滑到 下标3..6，子串 GATC。还是没见过。

i=3 · 记账 seen[GATC]=1：新增「GATC → 1」。前 4 个窗口都是「第一次见」，一个没收。下一格要变天了。

i=4 · 窗口右滑[4,7] · 又是 ATCG!：窗口滑到 下标4..7，读出的子串又是 ATCG！seen 表里 ATCG 那行命中(蓝色)，开头下标0-3 的 ATCG 也点亮了——它要凑成第 2 次了。

i=4 · 计数升到 2 · 收进答案!：seen[ATCG] 从 1 升到 2，恰好等于 2 的这一刻，把 ATCG 收进答案。两段 ATCG(下标0-3 和 4-7)一起高亮。这就是滑窗 + 哈希计数的全部魔法。

i=5 · 窗口右滑[5,8]：继续滑到 下标5..8，子串 TCGT。注意它和 TCGA 只差最后一位，是个全新子串。

i=5 · 记账 seen[TCGT]=1：新增「TCGT → 1」。后面的子串都不会再重复了，但算法照样老老实实记完。

i=6 · 窗口右滑[6,9]：滑到 下标6..9，子串 CGTA，新子串。

i=6 · 记账 seen[CGTA]=1：新增「CGTA → 1」。还剩最后一个窗口位置。

i=7 · 末位窗口[7,10]：最后一个位置 下标7..10，窗口右端正好顶到末尾。子串 GTAT，再滑就出界了。

i=7 · 记账 seen[GTAT]=1 · 扫描完成：最后新增「GTAT → 1」，8 个窗口全部扫完。整张 seen 表里只有 ATCG 计数到了 2，所以答案就是 [ATCG]。

回放唯一重复子串：回放：绿色的两段 ATCG 就是被逮住的重复子串。真题把窗口长 4 换成 10、串换成那 32 字母，过程一模一样，最后得到 AAAAACCCCC、CCCCCAAAAA 两个。

哈希表把「这子串见过没」从 O(n) 查找降到 O(1)。窗口滑 n 步、每步 O(1)(子串长固定 10，截取是常数)，整体 O(n)。

如果写 ≥2，一个出现 3 次的子串会在第 2、3 次各收一次，答案里就重复了。只在恰好等于 2 的那一刻收，等于「第一次发现它重复」时收，之后再多次也不再收——这就是免去额外去重的关键。

雷区实演 · 循环上界写过头：如果上界写成 i < len，i=8 时窗口要盖下标 8..11，可下标 11 根本不存在(本串末尾是 10)，截出来是残缺子串。正确上界是 i ≤ len−4(真题 len−10)，到 i=7 就停。

边界三连：注意 串长 < 10 时一个窗口都放不下，循环根本不进，返回空——`i+10 ≤ len` 的写法天然处理了这个边界，无需特判。

面试追问：能答出「2位编码 + 滚动哈希把子串压成 int」是这题的进阶加分点,体现你懂得用题目约束(只有4种字母)做空间优化。