题目分析

本题难度不大，基础解法小伙伴们一定要能迅速手撕出来。本题还引入了一个扩展的方法—字符串哈希，小伙伴们感兴趣可以了解一下。

滑动窗口

这个题目滑窗的思想，小伙伴们一定要掌握，题目暗示的非常明显，长度为10，那么窗口的大小是固定的。只要移动窗口，并将字符串加入哈希表即可。

因为窗口大小为常数10，算法的时间复杂度为O(n)，空间复杂度为O(n)。

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

字符串哈希

字符串哈希可以参考字符串哈希，里面有详细的思路和证明

这里直接给出代码，算法的时间复杂度为O(n)，空间复杂度为O(n)。

本题中b选择27就会产生冲突，无法通过第30个case，此时更换27为29，则可以通过。

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        int l = 10;
        int base = 1;
        int factor = 29;
        int[] curSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            curSum[i] = curSum[i - 1] * factor + s.charAt(i - 1) - 'a';
        }
        for (int i = 0; i < l; i++) {
            base *= factor;
        }
        List<String> res = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= n - l; i++) {
            int j = i + l;
            int cur = curSum[j] - curSum[i] * base;
            int cnt = map.getOrDefault(cur, 0);
            if (cnt == 1) {
                res.add(s.substring(i, i + l));
            }
            map.put(cur, cnt + 1);
        }
        return res;
    }
}

刷题总结

本题难度不大，可能官方想让我们学习的是滑动窗口的思路，这对于现在的面试笔试环境已经远远不够用了，我希望小伙伴可以看一看字符串哈希的扩展思路，对你会有很大帮助的。