【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; }

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; }

比较两个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; };