题目描述

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

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

样例

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

算法分析

• 枚举s字符串中长度是10的子字符串，存在哈希表中，并记录个数，最后枚举哈希表中哪个字符串出现的个数超过1，则记录下来

时间复杂度 $O(n)$

Java 代码

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> ans = new ArrayList<String>();
        HashMap<String , Integer> map = new HashMap<String, Integer>();
        for(int i = 0;i + 10 <= s.length();i ++)
        {
            String t = s.substring(i, i + 10);
            map.put(t, map.getOrDefault(t, 0) + 1);
        }
        for(Map.Entry<String, Integer> entry : map.entrySet())
        {
            if(entry.getValue() > 1)
                ans.add(entry.getKey());
        }
        return ans;
    }
}