LeetCode 187 重複 DNA 序列：位掩碼哈希優化空間

問題描述

給定 DNA 字符串（僅含 A, C, G, T），找出所有長度為 10 的重複子串。字符串長度可達 10^5，直接用 HashMap 存儲子串會超出內存限制。

核心優化：兩位編碼 + 滑動窗口位掩碼

DNA 只有 4 種字符，可用 2 bits 編碼：A=00, C=01, G=10, T=11。長度 10 的子串僅需 20 bits，完美放入 32 位整數。

算法流程

1. 預計算字符映射表
2. 滑動窗口維護當前 20-bit 哈希值：
   • 左移 2 位：`hash = (hash << 2) | map[c]`
   • 保留低 20 位：`hash &= (1 << 20) - 1`
3. 使用兩個 HashSet：
   • `seen`：記錄所有出現過的哈希值
   • `added`：記錄已加入結果的哈希值，避免重複輸出
4. 窗口形成後（i ≥ 9），檢查哈希值是否在 `seen` 中且不在 `added` 中，滿足則加入結果

優化實現（Java）

public List findRepeatedDnaSequences(String s) {
    List res = new ArrayList<>();
    if (s == null || s.length() < 11) return res;
    
    int hash = 0;
    Map map = new HashMap<>();
    map.put('A', 0); map.put('C', 1); map.put('G', 2); map.put('T', 3);
    
    Set seen = new HashSet<>();
    Set added = new HashSet<>();
    
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (i < 9) {
            hash = (hash << 2) | map.get(c);
        } else {
            hash = (hash << 2) | map.get(c);
            hash &= (1 << 20) - 1; // 保留低 20 位
            if (seen.contains(hash) && !added.contains(hash)) {
                res.add(s.substring(i - 9, i + 1));
                added.add(hash);
            } else {
                seen.add(hash);
            }
        }
    }
    return res;
}

關鍵點總結

• 位運算優先級：`(hash << 2) + map.get(c)` 必須加括號，否則 `+` 先於 `<<` 計算
• 滑動窗口邊界：前 9 個字符只構建哈希，不查重
• 空間優化：HashSet 遠小於 HashSet，滿足內存限制
• 時間複雜度：O(n)，單次遍歷

擴展應用

此技巧適用於所有小字符集、固定長度子串查重問題，如基因序列分析、文本指紋檢測、滾動哈希（Rabin-Karp）算法的核心思想。