重复的DNA序列

hash + 滑动窗口 + 位运算

所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：

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

示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

单单哈希表：

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int l = 10;
        vector<string> ans;
        map<string, int> cnt;
        int n = s.size();//s.size()返回的不是 int
        for(int i = 0; i <= n - l; i++){
            string s1 = s.substr(i, l);
            cnt[s1]++;
            if(cnt[s1] == 2) ans.push_back(s1);
        }
        return ans;
    }
};

hash + 滑动窗口 + 位运算：

思路：

　　将字符串用 01 数字表示，ACGT 分别为 00 01 10 11，这样一个字符串可以用一个 整型数字表示（整型数字有32位）。

       使用一个滑行窗口，窗口大小为 10。一直往后滑行，每滑行一个字母，窗口都会改变，这样改变时间复杂度为 O(1)。

　　窗口改变的过程：

　　　　①：窗口往后移动一位，即二进制数左移两位（每个字母需要用2bit表示），x = x << 2；

　　　　②：新增一个数，x = x | b[ch]；

　　　　③：最前面的字母离开窗口，即把二进制数保留 20 位，x = x & (( 1 << 20 ) - 1)； 

　　所以总的思路就是：建立一个滑动窗口，遍历 n - l + 1次，每次改变窗口位置，随之改变 x （时间复杂度O(1)），然后判断 x 是否出现 2 次，就可以把 substr(i, l)放入 ans 里面。

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        int l = 10, n = s.size(), x = 0;
        vector<string> ans;
        map<char, int> b = {{'A',0},{'C',1},{'G',2},{'T',3}};
        map<int, int> cnt;
        for(int i = 0; i < l - 1; i++){
            x = (x << 2) | b[s[i]];
        }
        for(int i = 0; i <= n - l; i++){
            x = ((x << 2) | b[s[i + l - 1]]) & ((1 << (l * 2)) - 1);
            cnt[x]++;
            if(cnt[x] == 2) ans.push_back(s.substr(i, l));
        } 
        return ans;
    }
};