一、题目描述
所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
代码语言：javascript复制示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 105
s[i] 为 'A'、'C'、'G' 或 'T'二、解题思路
线性时间窗口切片 HashSet HashMap
沿长度为 N 的字符串移动长度为 L 的滑动窗口。 检查滑动窗口中的序列是否在 HashMap中。 如果是，则找到了重复的序列，将序列假如到HashSet中。 否则，将序列添加到 HashMap中。
三、代码
代码语言：javascript复制import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
HashSet<String> sites = new HashSet<String>();
HashMap map=new HashMap<>();
int n=s.length();
for(int i=0;i<n-9;i ){
String subStr=s.substring(i,i 10);
if(map.containsKey(subStr)){
sites.add(subStr);
}else{
map.put(subStr,1);
}
}
return new ArrayList<>(sites);
}
public static void main(String[] args) {
Solution solution=new Solution();
List<String> rs=solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
//List<String> rs=solution.findRepeatedDnaSequences("AAAAAAAAAAAAA");
for(String s:rs){
System.out.println(s);
}
}
}四、复杂度分析
时间复杂度：O((N−L)L)。在执行的循环中，有N−L 1 个长度为 L 的子字符串，这会导致 O((N−L)L) 时间复杂性。 空间复杂度：使用了 O((N−L)L) 去存储 HashSet，由于 L=10 最终为时间复杂度为O(N)。
