重复的DNA序列

题目描述
给定一个表示DNA序列的字符串 s，其只包含 A, C, G, T 四种字符。请你找出所有在DNA分子中出现不止一次的、长度为10的子串（连续）。将结果以任意顺序返回。

示例：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC", "CCCCCAAAAA"]
解释：长度为10的子串 "AAAAACCCCC" 和 "CCCCCAAAAA" 在字符串中各出现了两次。

解题过程

这个问题本质上是在一个长字符串中，找出所有长度为10的、重复出现的子串。由于DNA序列可能很长（例如人类基因组有约30亿个碱基对），因此需要一种高效的方法来检查和记录子串的出现情况。

步骤1：理解问题与暴力法的局限

最直接的想法是：遍历所有长度为10的子串，用一个集合记录已经出现过的子串，如果再次遇到相同的子串，就将其加入结果集。但这里有两个关键点：

1. 如何高效地存储和比较长度为10的子串？
2. 如何避免重复地将同一个子串多次加入结果集？

暴力法的伪代码：

result = []
seen = set()
for i from 0 to len(s)-10:
    substring = s[i:i+10]
    if substring in seen and substring not in result:
        result.append(substring)
    else:
        seen.add(substring)
return result

但这里子串存储为字符串，当序列很长时（例如长度为1e6），会创建大量子串对象，内存和比较开销较大。

步骤2：使用哈希表与整数编码优化

观察到DNA字符只有4种，可以用2位二进制表示：

• A -> 00
• C -> 01
• G -> 10
• T -> 11

这样，一个长度为10的子串可以用20位二进制数（即一个整数）唯一表示。这个整数可以作为子串的“指纹”（hash值）。

编码方法：
定义一个映射字典：{'A':0, 'C':1, 'G':2, 'T':3}。
对于一个子串，遍历其每个字符，计算：

key = 0
for ch in substring:
    key = (key << 2) | map[ch]

因为每个字符用2位表示，所以左移2位后加上新字符的编码。

滑动计算哈希值：
如果对每个子串都从头计算编码，时间复杂度是O(10N)。但我们可以利用滚动哈希的思想，在滑动窗口时高效更新哈希值：

设当前子串 s[i:i+10] 的编码为 hash。
当窗口向右滑动一位，新子串为 s[i+1:i+11]，其编码可以通过以下方式更新：

1. 去掉最左边的字符 s[i]：hash = hash & ((1 << 20) - 1) （实际上更高效的做法是下面这样）
2. 左移2位，加入新字符 s[i+10]。

更具体地：

• 窗口内的哈希值可以看作一个20位的整数。
• 滑动时，先左移2位（相当于乘以4），然后加上新字符的编码，最后只保留低20位（即与 (1<<20)-1 做按位与）。

实现细节：

map = {'A':0, 'C':1, 'G':2, 'T':3}
mask = (1 << 20) - 1  # 用于只保留低20位
if len(s) < 10: return []
hash = 0
# 计算第一个长度为10的子串的哈希
for i in range(10):
    hash = ((hash << 2) | map[s[i]]) & mask

然后从 i=10 开始循环：

seen = set()
result = set()  # 用集合避免重复添加相同子串
seen.add(hash)
for i in range(10, len(s)):
    # 去掉最左字符（已通过左移和mask自动处理），加入新字符
    hash = ((hash << 2) | map[s[i]]) & mask
    if hash in seen:
        # 找到重复，但我们需要记录具体的子串，或者用另一个集合记录已输出的哈希
        # 由于最终要输出字符串，可以在这里从s[i-9:i+1]获取子串加入结果集
        result.add(s[i-9:i+1])
    else:
        seen.add(hash)

注意：由于哈希值是一个整数，可能存在不同子串映射到同一个整数的情况（哈希冲突）。但这里因为我们使用20位完整编码（而非压缩），所以不同的子串一定有不同的编码，没有冲突。这种编码实际上是一种“完美哈希”。

步骤3：完整代码实现与解释

def findRepeatedDnaSequences(s: str):
    if len(s) < 10:
        return []
    
    # 字符到2位编码的映射
    char_map = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
    mask = (1 << 20) - 1  # 20位掩码，用于只保留低20位
    
    # 计算第一个长度为10的子串的编码
    key = 0
    for i in range(10):
        key = (key << 2) | char_map[s[i]]
    
    seen = set()
    result = set()
    seen.add(key)
    
    # 滑动窗口
    for i in range(10, len(s)):
        # 左移2位，加入新字符，保留低20位
        key = ((key << 2) | char_map[s[i]]) & mask
        if key in seen:
            # 注意子串起始位置是 i-9，结束位置是 i+1
            result.add(s[i-9:i+1])
        else:
            seen.add(key)
    
    return list(result)

时间与空间复杂度：

• 时间复杂度：O(N)，其中N是字符串长度。每个字符处理一次。
• 空间复杂度：O(N)，最坏情况下需要存储所有不同子串的哈希值。

步骤4：进一步思考与扩展

1. 如果序列更长（例如上亿长度）：此方法仍然有效，因为整数哈希值占用空间小。但 seen 集合可能很大，如果内存受限，可以使用布隆过滤器进行近似去重（但会有假阳性，需根据场景权衡）。
2. 如果允许匹配不精确（有误差）：例如在生物信息学中，有时允许少量错配，那么上述精确哈希不再适用，需要使用更复杂的算法（如最小哈希、感知哈希）。
3. 实际应用：该问题直接对应于生物信息学中的“重复DNA序列识别”，用于分析基因组中的重复片段，可能关联到遗传疾病或进化研究。

总结
本题展示了哈希算法在生物信息学中的一个典型应用：通过将固定长度子串编码为整数，利用滑动窗口和哈希集合，我们能在O(N)时间内高效找出所有重复序列。这种“编码+滑动哈希”的技巧，在处理固定长度模式匹配时非常有效，也是Rabin-Karp算法的核心思想之一。