# 题目: 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: 遍历 + 哈希表
遍历字符串，在遍历的时候，找出以当前字符为字符串开头的目标字符串s(这里使用了slice (opens new window)), 并将次数其存在哈希表中。
- 如果存在则加1
- 如果不存在则置1
最后再遍历一次哈希表，找到次数超过1的字符串。
为了减少时间复杂度，我们在第一次遍历的时候，可以对数字进行判断，如果数目为2，则加入到我们结果集中。
# 代码
var findRepeatedDnaSequences = function(s) {
let res = []
let map = new Map()
for(let i=0;i<s.length;i++){
let tempStr = s.slice(i,i+10)
map.set(tempStr, (map.get(tempStr) || 0) +1)
if(map.get(tempStr) === 2){
res.push(tempStr)
}
}
return res
};
# 哈希表 + 滑动窗口 + 位运算
这里将借助 整数映射 和 位运算 来得到刚才第一个算法中slice操作。
字符串中只包含4个字符，我们可以使用 2个比特进行表示：
- A 表示为二进制 00；
- C 表示为二进制 01；
- G 表示为二进制 10；
- T 表示为二进制 11。
如此一来，一个长为 10 的字符串就可以用 20 个比特表示，在JavaScript 一个数字，就有1024位，完全足够容纳该字符串，因此我们可以将 s 的每个长为 10 的子串用一个 int 整数表示（只用低 20 位）。
上述字符串数字是一一映射，每一个数字都对应着唯一个的字符串，因此我们可以将方法一中的哈希表改为存字符串的整数表示。如果每一次都重新计算字符串的整数表示，其复杂度与方法一没有区别。这里借助一个10位的滑动窗口来计算10位的整数表示。
设当前滑动窗口对于的整数为x，当我们要计算下一个字符串时，就将滑动窗口向右移一位，此时会有一个新的字符串进入窗口，以及窗口的最左边的字符离开窗口，这些操作对应的位运算：
- 滑动窗口右移一位：
x = x<<2，由于每个字符用2个比特，所以要左移2位 - 一个新的字符 ch 进入窗口：x = x | bin[ch]，这里的bin[ch]表示字符的二进制映射
- 窗口最左的字符离开窗口: x = x&((1<<20)-1), 因为我们只考虑底20位，可以直接将其他位置零来完成。即：
(1 << 20) - 1
将这三步合并，就可以用 O(1) 的时间计算出下一个子串的整数表示，即 x = ((x << 2) | bin[ch]) & ((1 << 20) - 1)。
# 代码
/**
* @param {string} s
* @return {string[]}
*/
var findRepeatedDnaSequences = function(s) {
if(s.length < 10) return []
let bin = new Map()
bin.set('A',0)
bin.set('C',1)
bin.set('G',2)
bin.set('T',3)
let res = []
let tempNum =0
let map = new Map()
// 第一个 10位数 这里不需要进行高位置零
for(let i=0;i<10;i++){
tempNum = (tempNum << 2) | bin.get(s[i]);
}
map.set(tempNum,1)
for(let i=10;i<s.length;i++){
// 注意 位运算的优先级
tempNum = ((tempNum << 2) | bin.get(s[i])) & ((1<<20)-1);
map.set(tempNum, (map.get(tempNum)||0) + 1 )
if(map.get(tempNum) === 2){
res.push(s.slice(i-9,i+1))
}
}
return res
};