题目描述：
DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。
- 例如，
"ACGAATTCCG"是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。
给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
提示：
0 <= s.length <= 10^5s[i] =='A'、'C'、'G'or'T'
解法一：哈希表
算法思路：
我们使用一个长度为 10 的滑动窗口来枚举所有长度为 10 的子串，使用一个哈希表来统计不同的子串出现的次数，最后返回哈希表中所有出现次数超过 1 次的子串。
代码实现：
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<>();
Map<String, Integer> map = new HashMap<>();
int n = s.length();
for(int i = 0; i <= n-10; i++){
String str = s.substring(i, i+10);
map.put(str, map.getOrDefault(str, 0) + 1);
}
for(Map.Entry<String, Integer> entry : map.entrySet()){
if(entry.getValue() > 1){
ans.add(entry.getKey());
}
}
return ans;
}
}
复杂度分析：
时间复杂度： O(nL)，其中 n 是字符串 s 的长度，L = 10 是目标子串的长度。
空间复杂度： O(nL)。
解法二：位运算
算法思路：
由于 s 中只含有 4 种字符，我们可以将每个字符用 2 个比特表示，即：
- A 表示为二进制 00；
- C 表示为二进制 01；
- G 表示为二进制 10；
- T 表示为二进制 11。
如此一来，一个长为 10 的字符串就可以用 20 个比特表示，而一个 int 整数有 32 个比特，足够容纳该字符串，因此我们可以将 s 的每个长为 10 的子串用一个 int 整数表示（只用低 20 位）。
注意到上述字符串到整数的映射是一一映射，每个整数都对应着一个唯一的字符串，因此我们可以将方法一中的哈希表改为存储每个长为 10 的子串的整数表示。
我们可以用一个大小固定为 10 的滑动窗口来计算子串的整数表示。设当前滑动窗口对应的整数表示为 x，当我们要计算下一个子串时，就将滑动窗口向右移动一位，此时会有一个新的字符进入窗口，以及窗口最左边的字符离开窗口，这些操作对应的位运算，按计算顺序表示如下：
- 滑动窗口向右移动一位：
x = x << 2，由于每个字符用 2 个比特表示，所以要左移 2 位； - 一个新的字符 ch 进入窗口：
x = x | bin[ch]，这里 bin[ch]] 为字符 ch 的对应二进制； - 窗口最左边的字符离开窗口：
x = x & ((1 << 20) - 1)，由于我们只考虑 x 的低 20 位比特，需要将其余位置零，即与上(1 << 20) - 1。
将这三步合并，就可以用 O(1) 的时间计算出下一个子串的整数表示，即 x = ((x << 2) | bin[ch]) & ((1 << 20) - 1)。
代码实现：
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<>();
int n = s.length();
if (n <= 10) {
return ans;
}
int[] bin = new int[26];
bin['C' - 'A'] = 1;
bin['G' - 'A'] = 2;
bin['T' - 'A'] = 3;
int x = 0;
for (int i = 0; i < 10; ++i) {
x = (x << 2) | bin[s.charAt(i) - 'A'];
}
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(x, 1);
for (int i = 10; i < n; ++i) {
x = ((x << 2) | bin[s.charAt(i) - 'A']) & ((1 << 20) - 1);
int count = cnt.getOrDefault(x, 0);
if (count == 1) {
ans.add(s.substring(i - 9, i + 1));
}
cnt.put(x, count + 1);
}
return ans;
}
}
复杂度分析：
时间复杂度： O(n)，其中 n 是字符串 s 的长度。
空间复杂度： O(n)。
