重复的DNA序列（JS实现）

1 题目
所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来查找目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
示例：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”, “CCCCCAAAAA”]

链接：https://leetcode-cn.com/problems/repeated-dna-sequences

2 思路
这道题思路很简单，就是利用哈希表来记录遇到子串的次数，但每次计算hash值时，可以使用Rabin-Karp 旋转哈希算法根据上个子串的hash在O（1）的时间内计算下一个子串的hash

3代码
/**
* @param {string} s
* @return {string[]}
*/
var findRepeatedDnaSequences = function(s) {
let result = [];
if (s.length <= 10) return result;

let map = {‘A’: 0, ‘C’: 1, ‘G’: 2, ‘T’: 3};
let map1 = {};
let tempNum = Math.pow(4, 9);

let txtHash = computeHash(s, 0, 10); //计算首次hash值

for (let i=0; i<=s.length-10; i++) {
if (i !==0 ) txtHash = (txtHash – map[s[i-1]] * tempNum) * 4 + map[s[i+9]]; //根据上次子串hash推导当前子串的hash
if (!map1[txtHash]) {
map1[txtHash] = 1;
} else if (map1[txtHash] === 1) {
result.push(s.substr(i, 10));
map1[txtHash]++;
}
}

function computeHash(s, start, len) {
let hash = 0;
for (let i=0; i<len; i++) {
hash += map[s[i+start]] * Math.pow(4, len – i – 1);
}
return hash;
}

return result;
};