哈希算法题目：重复的DNA序列

题目描述：
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串中出现超过一次。

示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

解题过程：

1. 问题分析

   • 我们需要在给定的DNA字符串中找出所有长度为10的子串
   • 这些子串必须在整个字符串中出现至少2次
   • 输出结果中不能包含重复的子串

2. 基本思路

   • 遍历字符串，提取所有长度为10的子串
   • 使用哈希表记录每个子串出现的次数
   • 当某个子串出现次数达到2次时，将其加入结果集

3. 详细步骤

   • 步骤1：创建哈希表来存储子串和出现次数的映射
   • 步骤2：遍历字符串，从索引0开始到len(s)-10结束
   • 步骤3：对于每个起始位置i，提取子串s[i:i+10]
   • 步骤4：在哈希表中更新该子串的出现次数
   • 步骤5：当某个子串的出现次数恰好为2时，将其加入结果（避免重复添加）

4. 优化考虑

   • 直接存储字符串子串可能占用较多内存
   • 可以使用整数编码来压缩存储：将A、C、G、T分别编码为00、01、10、11
   • 这样每个长度为10的子串可以用20位整数表示，大大节省空间

5. 整数编码实现

   • 创建字符到编码的映射：{'A':0, 'C':1, 'G':2, 'T':3}
   • 使用位运算：每次左移2位，然后加上当前字符的编码
   • 使用掩码0xFFFFF（20位掩码）来保持整数的有效性

6. 完整算法流程

   • 如果字符串长度小于等于10，返回空列表
   • 初始化哈希表和结果列表
   • 计算第一个长度为10的子串的整数编码
   • 遍历字符串，滑动更新整数编码
   • 根据出现次数判断是否加入结果

这种方法的时间复杂度是O(n)，空间复杂度是O(n)，其中n是字符串长度。