187.重复的DNA序列.md

方法一：滑动窗口 + 哈希表

从左向右依次取长度为10的子串，判断它在哈希表中出现的次数是否是1（防止重复添加），如果之前出现过一次现在又出现一次那么就把这个子串添加到结果集合中。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String str = s.substring(i, i + 10);
            int cnt = map.getOrDefault(str, 0);
            if (cnt == 1) res.add(str);
            map.put(str, cnt + 1);
        }
        return res;
    }
}

方法二：字符串哈希

在一个字符串中寻找重复的连续子串可以使用字符串哈希法。

class Solution {
    int P = 131313;
    int[] h = new int[100010], p = new int[100010];
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<>();
        p[0] = 1;
        int n = s.length();
        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * P + s.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i + 10 - 1 <= n; i++) {
            int j = i + 10 - 1;
            int hash = h[j] - h[i - 1] * p[j - i + 1];
            int cnt = map.getOrDefault(hash, 0);
            if (cnt == 1) res.add(s.substring(i - 1, i + 10 - 1));
            map.put(hash, cnt + 1);
        }
        return res;
    }
}

*假设你要将字符串 abcd hash化成十进制的数，则 a = 1,ab = 12,abc=123,abcd = 1234。现在要求bcd 即abcd[1,3]的哈希值,是不是1234-1000（等价于 1234-1*10^3)在计算的过程中我们会另外开一个乘方数组记录某一个位置的位数即p数组,上述情况p[0]=1,p[1]=10,p[2]=100,p[3]=1000即hash(bcd)=hash(abcd)-hash(a)p[3-1+1]