187. 重复的DNA序列

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

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

示例 1：

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

示例 2：

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

提示：

• 0 <= s.length <= 105
• s[i] 为 'A'、'C'、'G' 或 'T'

   1 import java.util.ArrayList;
   2 import java.util.HashMap;
   3 import java.util.List;
   4 import java.util.Map;
   5 
   6 public class FindRepeatedDnaSequences {
   7     public List<String> findRepeatedDnaSequences(String s) {
   8         HashMap<String, Integer> map = new HashMap<>();
   9         List<String> strings = new ArrayList<>();
  10         if (s.length()<=10){
  11             return strings;
  12         }else{
  13             for (int i = 0; i <= s.length()-10; i++) {
  14                 String temp=s.substring(i,i+10);
  15                 if (map.containsKey(temp)){
  16                     map.put(temp,map.get(temp)+1);
  17                 }else{
  18                     map.put(temp,1);
  19                 }
  20             }
  21             for (Map.Entry<String, Integer> entry : map.entrySet()) {
  22                 if (entry.getValue()>1){
  23                     strings.add(entry.getKey());
  24                 }
  25             }
  26             return strings;
  27         }
  28     }
  29 
  30     public static void main(String[] args) {
  31         System.out.println(new FindRepeatedDnaSequences().findRepeatedDnaSequences("AAAAAAAAAAA"));
  32     }
  33 }

  长度小于10时，直接返回空数组。长度大于10时，遍历所有子串，利用hashmap判断该子串的次数，最后遍历hashmap，添加所有超过一次的子串到结果数组中。