LeetCode 187. 重复的DNA序列

约 5 分钟
文章信息 10 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 华为 微软 快手 虾皮
标签
字符串 哈希表 位运算 滑动窗口 哈希函数 滚动哈希

题目描述

✅ 187. 重复的DNA序列

image-20260928235002674

题意分析

找出所有出现至少两次、长度恰好为 10 的连续 DNA 片段。不同出现位置可以重叠，但同一个片段在答案中只返回一次，返回顺序不限。

每个片段只包含 A、C、G、T 四种字符，可以把它们压缩成一个整数，用整数记录出现次数。

解法：固定窗口 + 2 位滚动编码

核心思路

[!blue]

将 A、C、G、T 分别映射为 0、1、2、3，每个字符恰好占两位。长度为 10 的窗口便对应一个 20 位整数，范围是 0 到 2^20-1，可以直接作为计数数组的下标。

这是固定长度的四进制表示：每两位都对应唯一的字符，按顺序解码就能恢复整个窗口。因此不同的完整窗口不会得到相同编码，即使开头含有编码为 0 的 A 也不影响唯一性。

扫描到新字符时，将旧 code 左移两位，为新字符空出最低两位，再用按位或放入新编码。最后与 MASK = (1 << 20) - 1 按位与，只保留低 20 位：最早的字符被移到掩码之外，留下的正好是最近 10 个字符，无需重新扫描整个窗口。

下标达到 9 后才形成第一个完整窗口，此时开始更新 count[code]。次数从 1 变为 2 时，把当前长度为 10 的子串加入答案；之后次数继续增加，但不再收录。这样同时保证每个答案确实重复，并且只输出一次。

解题步骤

  1. 准备大小为 2^20 的计数数组、低 20 位掩码，以及初始为 0 的 code。
  2. 依次读入每个字符，执行“左移两位、加入新编码、保留低 20 位”的滚动更新。
  3. 若当前位置 i < 9，只更新编码，不计数；这时得到的还不是长度为 10 的片段。
  4. 从 i = 9 开始，将 count[code] 加一。若它恰好等于 2，收录区间 [i-9, i+1) 的子串。
  5. 扫描结束后返回答案。字符串不足 10 个字符时不会统计窗口，结果自然为空；恰好 10 个字符时最多出现一次，也不会加入答案。

代码实现

class Solution {
    private static final int WINDOW = 10;
    private static final int MASK = (1 << (WINDOW * 2)) - 1;

    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        int[] count = new int[1 << (WINDOW * 2)];
        int code = 0;

        for (int i = 0; i < s.length(); i++) {
            // 左移加入新字符后只留低二十位，准确表示最近十个字符。
            code = ((code << 2) | encode(s.charAt(i))) & MASK;

            // 窗口满十个字符才计数；只在第二次出现时报告一次。
            if (i >= WINDOW - 1 && ++count[code] == 2) {
                res.add(s.substring(i - WINDOW + 1, i + 1));
            }
        }

        return res;
    }

    // 四种字符显式映射到零至三，每个字符严格占两位。
    private int encode(char nucleotide) {
        return switch (nucleotide) {
            case 'A' -> 0;
            case 'C' -> 1;
            case 'G' -> 2;
            // 题目保证剩余字符只会是 'T'。
            default -> 3;
        };
    }
}

func findRepeatedDnaSequences(s string) []string {
    const window = 10
    const mask = 1<<(window*2) - 1

    count := make([]int, 1<<(window*2))
    res := make([]string, 0)
    code := 0
    for i := 0; i < len(s); i++ {
        // 左移加入新字符后只留低二十位，准确表示最近十个字符。
        code = (code<<2 | encodeNucleotide(s[i])) & mask
        // 窗口满十个字符才计数；只在第二次出现时报告一次。
        if i >= window-1 {
            count[code]++
            if count[code] == 2 {
                res = append(res, s[i-window+1:i+1])
            }
        }
    }
    return res
}

// 四种字符显式映射到零至三，每个字符严格占两位。
func encodeNucleotide(nucleotide byte) int {
    switch nucleotide {
    case 'A':
        return 0
    case 'C':
        return 1
    case 'G':
        return 2
    // 题目保证剩余字符只会是 'T'。
    default:
        return 3
    }
}

复杂度分析

设字符串长度为 n。

  • 时间复杂度：$O(n+2^{20})$，包含计数数组的初始化。每个字符只进行常数次位运算与计数，收录的子串长度固定为 10。
  • 空间复杂度：$O(2^{20})$，用于计数数组，不计返回结果。窗口长度固定为 10，所以这部分空间不随 n 增长。

关键点总结

[!green]

  • 四种字符恰好用两位表示，十个字符得到可直接索引的 20 位编码。
  • 左移加入新字符，掩码删除最早字符，每一步都准确表示当前窗口。
  • 只有完整窗口才参与计数，只在第二次出现时收录答案。

易错点总结

[!yellow]

  • 直接用字符减去 A 作为编码：四种字母在字母表中并不连续，结果可能超过两位，必须映射到 0...3。
  • 忘记保留低 20 位：旧窗口之外的字符仍会留在编码中，不能准确代表最近 10 个字符，还可能越过计数数组范围。
  • 窗口未满就计数：短前缀与前面补了 A 的完整窗口可能具有相同整数编码，固定长度的唯一性只适用于完整窗口。
  • 次数大于等于 2 就收录：第三次及之后出现会重复加入答案，应判断是否恰好变成 2。
  • 子串右边界写成 i：Java、Go 截取子串的右端不包含在内，包含当前字符需要写成 i+1。

相似题目

题目 难度 关联与区别
438. 找到字符串中所有字母异位词 中等 同样扫描固定长度窗口，本题签名必须保留字符顺序，频次表无法区分不同DNA序列。
1044. 最长重复子串 困难 原题寻找任意长度的最长重复子串，本题长度固定为10，可用固定窗口编码判重。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/56017792
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！