leetcode

中等哈希表双指针字符串滑动窗口

方法1 滑动窗口

var checkInclusion = function (s1, s2) {
  // 比较两个不同的 arr 是否相同
  const compareDiffArr = (arr1, arr2) => {
    return [...arr1].sort().join() === [...arr2].sort().join()
  }
  const len1 = s1.length, len2 = s2.length,
    arr1 = [], arr2 = [];
  for (let i = 0; i < len1; i++) {
    arr1.push(s1[i]);
    arr2.push(s2[i]);
  }
  for (let i = len1; i < len2; i++) {
    if (compareDiffArr(arr1, arr2)) return true;
    arr2.splice(0, 1); // 窗口左侧向右边滑动，收缩窗口
    arr2.push(s2[i]); // 窗口右侧向右边滑动，扩展窗口
  }
  return compareDiffArr(arr1, arr2);
};

上述做法应该是可行的，不过执行超时。。。

var checkInclusion = function (s1, s2) {
  const len1 = s1.length, len2 = s2.length;
  if (len1 > len2) return false;
  const count1 = new Array(26).fill(0), // 记录 s1 中每个字符
    count2 = new Array(26).fill(0); // 记录 s2 中每个字符
  // 初始化 count
  for (let i = 0; i < len1; i++) {
    ++count1[s1[i].charCodeAt() - 97];
    ++count2[s2[i].charCodeAt() - 97];
  }
  const compare = () => count1.toString() === count2.toString();
  for (let i = len1; i < len2; i++) {
    if (compare()) return true;
    // 滑动窗口
    --count2[s2[i - len1].charCodeAt() - 97];
    ++count2[s2[i].charCodeAt() - 97];
  }
  return compare();
};

重点：找到字母对应的下标。

一个萝卜一个坑，找到对应的坑后，再执行相应地操作。

方法2