重复的DNA序列

题目

题目来源：力扣（LeetCode

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

示例 1：

输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
输出：[“AAAAACCCCC”,”CCCCCAAAAA”]
示例 2：

输入：s = “AAAAAAAAAAAAA”
输出：[“AAAAAAAAAA”]

思路分析

滑动窗口 + 哈希集合

沿长度为 N 的字符串移动长度为 L 的滑动窗口。检查滑动窗口中的序列是否在 HashSet 中。
如果是，则找到了重复的序列。更新输出。
否则，将序列添加到 HashSet 中。

/**
 * @param {string} s
 * @return {string[]}
 */
var findRepeatedDnaSequences = function (s) {
    if (s.length < 11) return [];
    let n = s.length, map = new Map(), left = 0, right = 10, res = [];
    // 沿长度为 n 的字符串移动长度为 10 的滑动窗口
    while (right <= n) {
      let cur = s.substring(left, right);
      // 检查滑动窗口中的序列是否在 HashSet 中，统计出现的次数，出现次数达到2，就是所求答案
      map.set(cur, map.has(cur) ? map.get(cur) + 1 : 1);
      left++;
      right++;
    }
    for (let [k, v] of map) {
      if (v > 1) res.push(k);
    }
    return res;
};