前言

LeetCode 187 要求：给定一个只包含'A'、'C'、'G'、'T'的字符串，找出所有长度为 10、且在字符串中出现不止一次的连续子串。返回结果中每个子串只出现一次，顺序不限。

这道题的核心是"滑动窗口 + 去重"。窗口长度固定为 10，从下标 0 开始每次右移一位，把窗口内的子串放进集合；如果集合里已经有了，说明这是重复出现的，再放进结果集合避免重复输出。

常见误解是"找到重复后直接 push 进结果"。如果某个子串出现三次，它会在第二次和第三次都被判定为重复，结果里就会出现两份。必须再用一个集合记录"已经加入结果的子串"。

另一个常见问题是下标边界。std::string::substr(pos, len)在pos > size()时抛std::out_of_range，循环条件写错就会越界。本文给出哈希集合法和按位编码两种实现，并比较它们的复杂度。

一、朴素思路与复杂度

长度为 n 的字符串，长度为 10 的窗口一共有 n - 9 个（n >= 10）。每个窗口取出 10 个字符，构造一个std::string，插入哈希集合。

• 
  
• 取子串：O(10)，常数；
• 
  
• 哈希：O(10)；
• 
  
• 总时间：O(10n)，通常简写为 O(n)；
• 
  
• 空间：最多 n - 9 个长度为 10 的字符串，O(n)。
• 
  

如果 n 远大于 10，常数 10 不影响渐近复杂度，但每个窗口都要构造一个短字符串，堆分配的次数不少。按位编码可以把每个窗口压成一个 20 位整数，避免这些分配。

二、哈希集合实现

用两个集合：seen记录所有出现过的窗口，recorded记录已经写进结果的窗口。

// 适用于 C++17
#include <cstddef>
#include <string>
#include <unordered_set>
#include <vector>

std::vector<std::string> findRepeatedDnaSequences(const std::string &s)
{
std::vector<std::string> result;

if (s.size() < 10) {
return result; // 长度不足，不可能有答案
}

std::unordered_set<std::string> seen;
std::unordered_set<std::string> recorded;

for (std::size_t i = 0; i + 10 <= s.size(); ++i) {
std::string window = s.substr(i, 10);

if (!seen.insert(window).second) { // 插入失败说明已存在
if (recorded.insert(window).second) {
result.push_back(window);
}
}
}
return result;
}

insert返回std::pair<iterator, bool>，第二个成员表示是否真的插入了新元素。插入失败就说明集合里已经有这个值，也就是重复出现。

循环条件i + 10 <= s.size()保证substr的起点和长度都合法。i是std::size_t，不会出现负数；但要注意i + 10在极端大的字符串上可能溢出，实际输入远达不到这个规模。

三、按位编码优化

DNA 只有四种字符，每个字符用 2 个比特就能表示：

长度 10 的窗口正好占 20 位，可以放进一个 32 位无符号整数。窗口右移一位时，把旧值左移 2 位、或上新字符的编码，再用 20 位掩码截断，就得到新窗口的编码。这就是滚动哈希（rolling hash）的思想，只不过这里是无冲突的精确编码。

// 适用于 C++17
#include <cstddef>
#include <string>
#include <unordered_set>
#include <vector>

std::vector<std::string> findRepeatedDnaSequencesFast(const std::string &s)
{
std::vector<std::string> result;

if (s.size() < 10) {
return result;
}

const auto code = [](char c) -> unsigned {
switch (c) {
case 'A': return 0u;
case 'C': return 1u;
case 'G': return 2u;
default: return 3u; // 'T'
}
};

const unsigned mask = (1u << 20) - 1u;

unsigned key = 0u;
for (std::size_t i = 0; i < 10; ++i) {
key = (key << 2) | code(s[i]);
}

std::unordered_set<unsigned> seen;
std::unordered_set<unsigned> recorded;
seen.insert(key);

for (std::size_t i = 10; i < s.size(); ++i) {
key = ((key << 2) | code(s[i])) & mask;

if (!seen.insert(key).second) {
if (recorded.insert(key).second) {
result.push_back(s.substr(i - 9, 10));
}
}
}
return result;
}

mask是低 20 位全 1。不加掩码的话，key会不断左移，高位越积越多，虽然低 20 位仍然正确，但不同窗口的整数值会互相干扰。加上掩码后，key严格对应最近 10 个字符。

i - 9是当前窗口的起始下标：窗口覆盖[i-9, i]，共 10 个字符。

四、两种实现的比较

按位编码在常数因子上更省，但渐近复杂度仍是 O(n)。如果面试时不确定编码细节，写字符串版本更稳妥；把优化思路讲清楚，比写出一个边界错误的快速版本更好。

五、结果顺序与判题

题目说"顺序不限"，所以返回的vector按什么顺序排列都可以。unordered_set的遍历顺序不稳定，但这不影响正确性。不要为了让输出"看起来有序"而额外排序，那会多出 O(k log k) 的开销。

如果平台要求固定顺序，可以在最后对结果排序，或者按首次出现的下标记录顺序。

六、边界与示例推演

题目常见的边界有三类：

• 
  
• 长度小于 10：直接返回空结果，循环不应进入。
• 
  
• 长度正好为 10：只有一个窗口，不可能重复，结果为空。
• 
  
• 全部字符相同：每个窗口都相同，结果只包含这一个子串，且只出现一次。
• 
  

以"AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"为例，按语义推演，前 10 位是"AAAAACCCCC"，下标 5 到 14 是"CCCCCAAAAA"，这两个子串在后面都再次出现，因此结果是这两个。注意"AAAAACCCCC"在字符串里出现了两次，但结果中只能有一份，这正是第二个集合的作用。

再看"AAAAAAAAAAAA"（12 个 A）：所有窗口都是"AAAAAAAAAA"，它出现了 3 次，结果里仍然只有一个元素。如果只用一个集合，代码会在第二次和第三次都把它加入结果，得到重复项。

常见坑点

1. 
   
2. ❌ 找到重复就直接push_back，同一子串出现三次时结果重复。
3. 
   

✅ 用第二个集合记录已加入结果的键。

1. 
   
2. ❌ 循环写成i <= s.size()，substr越界抛异常。
3. 
   

✅ 条件写i + 10 <= s.size()，保证窗口完整。

1. 
   
2. ❌ 对长度小于 10 的字符串仍进入循环。
3. 
   

✅ 开头判断s.size() < 10直接返回空结果。

1. 
   
2. ❌ 滚动编码忘记加 20 位掩码。
3. 
   

✅key = ((key << 2) | code(c)) & ((1u << 20) - 1u);。

1. 
   
2. ❌ 用有符号int做左移，最高位行为不确定。
3. 
   

✅ 用unsigned保存编码。

1. 
   
2. ❌ 把substr(i - 9, 10)写成substr(i - 10, 10)，窗口错位。
3. 
   

✅ 当前字符下标为 i 时，窗口起点是i - 9。

1. 
   
2. ❌ 假设unordered_set的遍历顺序稳定，据此构造输出。
3. 
   

✅ 顺序不作保证；需要固定顺序就显式排序。

1. 
   
2. ❌ 用普通哈希值代替原串做去重，忽略碰撞。
3. 
   

✅ 要么存原串，要么用无冲突的精确编码；仅靠哈希值可能把不同子串当成同一个。

总结

这道题的关键不是哈希本身，而是"窗口长度固定 + 两个集合去重"。把边界写对、把重复结果挡住，再用编码优化常数，就能得到一份既正确又清晰的实现。