)
前言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记录已经写进结果的窗口。// 适用于 C17#include cstddef#include string#include unordered_set#include vectorstd::vectorstd::string findRepeatedDnaSequences(const std::string s){std::vectorstd::string result;if (s.size() 10) {return result; // 长度不足不可能有答案}std::unordered_setstd::string seen;std::unordered_setstd::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::pairiterator, bool第二个成员表示是否真的插入了新元素。插入失败就说明集合里已经有这个值也就是重复出现。循环条件i 10 s.size()保证substr的起点和长度都合法。i是std::size_t不会出现负数但要注意i 10在极端大的字符串上可能溢出实际输入远达不到这个规模。三、按位编码优化DNA 只有四种字符每个字符用 2 个比特就能表示字符编码A00C01G10T11长度 10 的窗口正好占 20 位可以放进一个 32 位无符号整数。窗口右移一位时把旧值左移 2 位、或上新字符的编码再用 20 位掩码截断就得到新窗口的编码。这就是滚动哈希rolling hash的思想只不过这里是无冲突的精确编码。// 适用于 C17#include cstddef#include string#include unordered_set#include vectorstd::vectorstd::string findRepeatedDnaSequencesFast(const std::string s){std::vectorstd::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_setunsigned seen;std::unordered_setunsigned 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 个字符。四、两种实现的比较维度哈希字符串按位编码每个窗口的键std::string10 字节 可能的堆分配unsigned4 字节哈希计算遍历 10 个字符一次移位与或冲突由字符串相等保证正确编码一一对应无冲突代码复杂度低中可读性直接对应题意需要理解编码按位编码在常数因子上更省但渐近复杂度仍是 O(n)。如果面试时不确定编码细节写字符串版本更稳妥把优化思路讲清楚比写出一个边界错误的快速版本更好。五、结果顺序与判题题目说顺序不限所以返回的vector按什么顺序排列都可以。unordered_set的遍历顺序不稳定但这不影响正确性。不要为了让输出看起来有序而额外排序那会多出 O(k log k) 的开销。如果平台要求固定顺序可以在最后对结果排序或者按首次出现的下标记录顺序。六、边界与示例推演题目常见的边界有三类长度小于 10直接返回空结果循环不应进入。长度正好为 10只有一个窗口不可能重复结果为空。全部字符相同每个窗口都相同结果只包含这一个子串且只出现一次。以AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT为例按语义推演前 10 位是AAAAACCCCC下标 5 到 14 是CCCCCAAAAA这两个子串在后面都再次出现因此结果是这两个。注意AAAAACCCCC在字符串里出现了两次但结果中只能有一份这正是第二个集合的作用。再看AAAAAAAAAAAA12 个 A所有窗口都是AAAAAAAAAA它出现了 3 次结果里仍然只有一个元素。如果只用一个集合代码会在第二次和第三次都把它加入结果得到重复项。常见坑点❌ 找到重复就直接push_back同一子串出现三次时结果重复。✅ 用第二个集合记录已加入结果的键。❌ 循环写成i s.size()substr越界抛异常。✅ 条件写i 10 s.size()保证窗口完整。❌ 对长度小于 10 的字符串仍进入循环。✅ 开头判断s.size() 10直接返回空结果。❌ 滚动编码忘记加 20 位掩码。✅key ((key 2) | code(c)) ((1u 20) - 1u);。❌ 用有符号int做左移最高位行为不确定。✅ 用unsigned保存编码。❌ 把substr(i - 9, 10)写成substr(i - 10, 10)窗口错位。✅ 当前字符下标为 i 时窗口起点是i - 9。❌ 假设unordered_set的遍历顺序稳定据此构造输出。✅ 顺序不作保证需要固定顺序就显式排序。❌ 用普通哈希值代替原串做去重忽略碰撞。✅ 要么存原串要么用无冲突的精确编码仅靠哈希值可能把不同子串当成同一个。总结方案时间空间适用双哈希集合O(n)每窗口 10 次字符操作O(n)通用代码直观按位编码O(n)O(n)字符集小、追求常数优化排序后比较相邻O(n log n)O(n)不推荐慢且实现麻烦这道题的关键不是哈希本身而是窗口长度固定 两个集合去重。把边界写对、把重复结果挡住再用编码优化常数就能得到一份既正确又清晰的实现。
前言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记录已经写进结果的窗口。// 适用于 C17#include cstddef#include string#include unordered_set#include vectorstd::vectorstd::string findRepeatedDnaSequences(const std::string s){std::vectorstd::string result;if (s.size() 10) {return result; // 长度不足不可能有答案}std::unordered_setstd::string seen;std::unordered_setstd::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::pairiterator, bool第二个成员表示是否真的插入了新元素。插入失败就说明集合里已经有这个值也就是重复出现。循环条件i 10 s.size()保证substr的起点和长度都合法。i是std::size_t不会出现负数但要注意i 10在极端大的字符串上可能溢出实际输入远达不到这个规模。三、按位编码优化DNA 只有四种字符每个字符用 2 个比特就能表示字符编码A00C01G10T11长度 10 的窗口正好占 20 位可以放进一个 32 位无符号整数。窗口右移一位时把旧值左移 2 位、或上新字符的编码再用 20 位掩码截断就得到新窗口的编码。这就是滚动哈希rolling hash的思想只不过这里是无冲突的精确编码。// 适用于 C17#include cstddef#include string#include unordered_set#include vectorstd::vectorstd::string findRepeatedDnaSequencesFast(const std::string s){std::vectorstd::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_setunsigned seen;std::unordered_setunsigned 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 个字符。四、两种实现的比较维度哈希字符串按位编码每个窗口的键std::string10 字节 可能的堆分配unsigned4 字节哈希计算遍历 10 个字符一次移位与或冲突由字符串相等保证正确编码一一对应无冲突代码复杂度低中可读性直接对应题意需要理解编码按位编码在常数因子上更省但渐近复杂度仍是 O(n)。如果面试时不确定编码细节写字符串版本更稳妥把优化思路讲清楚比写出一个边界错误的快速版本更好。五、结果顺序与判题题目说顺序不限所以返回的vector按什么顺序排列都可以。unordered_set的遍历顺序不稳定但这不影响正确性。不要为了让输出看起来有序而额外排序那会多出 O(k log k) 的开销。如果平台要求固定顺序可以在最后对结果排序或者按首次出现的下标记录顺序。六、边界与示例推演题目常见的边界有三类长度小于 10直接返回空结果循环不应进入。长度正好为 10只有一个窗口不可能重复结果为空。全部字符相同每个窗口都相同结果只包含这一个子串且只出现一次。以AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT为例按语义推演前 10 位是AAAAACCCCC下标 5 到 14 是CCCCCAAAAA这两个子串在后面都再次出现因此结果是这两个。注意AAAAACCCCC在字符串里出现了两次但结果中只能有一份这正是第二个集合的作用。再看AAAAAAAAAAAA12 个 A所有窗口都是AAAAAAAAAA它出现了 3 次结果里仍然只有一个元素。如果只用一个集合代码会在第二次和第三次都把它加入结果得到重复项。常见坑点❌ 找到重复就直接push_back同一子串出现三次时结果重复。✅ 用第二个集合记录已加入结果的键。❌ 循环写成i s.size()substr越界抛异常。✅ 条件写i 10 s.size()保证窗口完整。❌ 对长度小于 10 的字符串仍进入循环。✅ 开头判断s.size() 10直接返回空结果。❌ 滚动编码忘记加 20 位掩码。✅key ((key 2) | code(c)) ((1u 20) - 1u);。❌ 用有符号int做左移最高位行为不确定。✅ 用unsigned保存编码。❌ 把substr(i - 9, 10)写成substr(i - 10, 10)窗口错位。✅ 当前字符下标为 i 时窗口起点是i - 9。❌ 假设unordered_set的遍历顺序稳定据此构造输出。✅ 顺序不作保证需要固定顺序就显式排序。❌ 用普通哈希值代替原串做去重忽略碰撞。✅ 要么存原串要么用无冲突的精确编码仅靠哈希值可能把不同子串当成同一个。总结方案时间空间适用双哈希集合O(n)每窗口 10 次字符操作O(n)通用代码直观按位编码O(n)O(n)字符集小、追求常数优化排序后比较相邻O(n log n)O(n)不推荐慢且实现麻烦这道题的关键不是哈希本身而是窗口长度固定 两个集合去重。把边界写对、把重复结果挡住再用编码优化常数就能得到一份既正确又清晰的实现。
