重复的DNA序列 题目描述 给定一个表示 DNA 序列的字符串 s ，只包含 A 、 C 、 G 和 T 四种字符。返回所有在 s 中出现次数超过一次的 长度为 10 的子串。可以按任意顺序返回答案。 示例： 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出：[ "AAAAACCCCC", "CCCCCAAAAA" ] 解题过程 问题分析 DNA 序列仅由 4 种字符组成，需要找出所有长度为 10 且出现次数 > 1 的子串。 若直接枚举所有长度为 10 的子串并用哈希表计数，时间复杂度为 O(10n) = O(n)，但需注意子串数量可能很大（n 可达 10^5），需优化存储。 关键优化思路 长度为 10 的子串可能有很多重复，但字符种类只有 4 个，可以用 2 位二进制表示一个字符： A →00, C →01, G →10, T →11。 每个长度为 10 的子串可映射为一个 20 位的整数（因为 10 字符 × 2 位/字符 = 20 位），该整数可存入整型变量（32 位足够），节省空间。 具体步骤 若字符串长度 ≤ 10，直接返回空列表。 初始化哈希表 seen 记录子串出现次数，以及结果列表 res 。 首先处理前 10 个字符，计算对应的 20 位整数 key ： 遍历前 10 个字符，每次将 key 左移 2 位，并加上当前字符的二进制编码。 将 key 加入 seen ，计数为 1。 从第 11 个字符开始（索引 10），滑动窗口处理： 移除窗口最左字符的影响： key = key & ((1 << 20) - 1) 实际上不需要，因为左移后超出 20 位的部分会被掩码去除，但更准确的做法是每次左移 2 位后，用掩码 mask = (1 << 20) - 1 取低 20 位： key = ((key << 2) & mask) | char_code 。 加入新字符的编码。 更新 seen 中 key 的计数，若计数刚好为 2，则将当前子串加入结果（避免重复添加）。 字符到二进制映射 定义映射字典： encode = {'A': 0, 'C': 1, 'G': 2, 'T': 3} ，每个字符对应 0~3，正好用 2 位表示。 举例说明 以 s = "ACGTACGTAC" 前 10 个字符为例： 初始 key = 0 处理 'A'：key = (0 < < 2) | 0 = 0 处理 'C'：key = (0 < < 2) | 1 = 1 继续直到得到 20 位的 key。 滑动窗口时，左移 2 位，去掉最左字符的位，加入新字符的位。 代码实现要点 掩码 mask = (1 < < 20) - 1，即二进制的低 20 位全 1。 当 seen[key] == 2 时才加入结果，避免重复。 子串通过当前窗口起始位置 i-9 到 i+1 切片得到。 总结 本题通过将 DNA 字符编码为 2 位二进制，将子串转换为 20 位整数，显著减少哈希表的存储开销，同时利用滑动窗口在 O(1) 时间内更新整数键值，整体时间复杂度 O(n)，空间复杂度 O(n)。