【leetcode每日一题】【滑动窗口长度固定】案例

567. 字符串的排列 长度不变

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 ****的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串

思路：s1长度固定的窗口里的hash表和s2 要一致

• 用一个s1Map 保存 s1出现的字符和个数。
• 遍历 s2，维护窗口里的map

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  let map = new Map();
  for (let i = 0; i < s1.length; i++) {
    map.set(s1[i], map.get(s1[i]) + 1 || 1);
  }

  let left = 0;
  let s1Map = new Map();
  for (let i = 0; i < s2.length; i++) {
   // 扩大窗口，维护窗口里字符出现的个数
    s1Map.set(s2[i], s1Map.get(s2[i]) + 1 || 1);

	// 如果窗口满足条件
    if (i - left + 1 === s1.length) {

		// 满足要求的 ，更新答案
      if (isSameMap(s1Map, map)) {
        return true;
      }

		// 缩小窗口，维护窗口减少的字符串
      s1Map.set(s2[left], s1Map.get(s2[left]) - 1);
      if (s1Map.get(s2[left]) === 0) {
        s1Map.delete(s2[left]);
      }
      left++;
    }
  }
  return false;
};

function isSameMap(map1, map2) {
    if (map1.size !== map2.size) {
        return false;
    }
    for (let key of map1.keys()) {
        if (map1.get(key) !== map2.get(key)) {
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

438 找到字符串中所有字母异位词 长度固定。

上一道题是是否有，这道题是如果有，找出所有答案。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let map = new Map();
    for(let i = 0; i < p.length; i++){
        map.set(p[i], map.get(p[i]) + 1 || 1);
    }
    let left = 0;
    let sMap = new Map();
    let res = [];
    for(let i = 0; i < s.length; i++){
    // 扩大窗口，维护窗口里字符出现的个数
        sMap.set(s[i], sMap.get(s[i]) + 1 || 1);

        // 如果到达了限定长度
        if(i-left+1 === p.length){

            // 判断是否能够更新答案
            if(isSameMap(sMap, map)){
                res.push(left);
            }

            // 缩小窗口。
            sMap.set(s[left], sMap.get(s[left]) - 1);
            if(sMap.get(s[left]) === 0){
                sMap.delete(s[left]);
            }
            left++
        }
    }
    return res;
};

// 比较两个map是否相同
function isSameMap(map1, map2) {
    if (map1.size !== map2.size) {
        return false;
    }
    for (let key of map1.keys()) {
        if (map1.get(key) !== map2.get(key)) {
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

比较两个map是否相同。

可以使用map，也可以使用一个26位数组（都是小写或者都是大写），然后再比较两个数组是否相同。

方法二，使用频数数组。

var findAnagrams = function (s, p) {
  let pArr = new Array(26).fill(0);
  for (let i = 0; i < p.length; i++) {
    pArr[p.charCodeAt(i) - "a".charCodeAt(0)]++;
  }

  let sArr = new Array(26).fill(0);
  let res = [];
  let left = 0;
  for (let i = 0; i < s.length; i++) {
    sArr[s[i].charCodeAt(0) - "a".charCodeAt(0)]++;

    if (i - left + 1 === p.length) {
      if (sArr.toString() === pArr.toString()) {
        res.push(left);
      }
      sArr[s[left].charCodeAt(0) - "a".charCodeAt(0)]--;
      left++;
    }
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22