综述

通常分为两段式，先计算一个定长窗口，然后再向右依次滑动窗口，每滑动一次窗口，更新一次结果集。

模板

  1. 写法一：用两个指针l, r
  3. let l = 0, r = 0, ans = 结果集
  4. while(r < k) {
  5.   计算窗口
  6.   r++
  7. }
  8. while( r < |len|) {
  9.   滑动窗口，加入新的r元素，去除旧的l元素，r++，l++；
  10.   更新结果集
  11. }
  12. return ans;
  14. 写法二：只使用一个主指针r, 由于是定长，所以可以直接计算l的位置。
  16. let r = 0, ans = 结果集
  17. while(r < k) {
  18.   计算窗口
  19.   r++
  20. }
  21. while( r < |len|) {
  22.   滑动窗口，加入新的r元素，去除旧的l元素，r++，l = r - k；
  23.   更新结果集
  24. }
  25. return ans;

例题

【求和】1176. 健身计划评估

难度简单17收藏分享切换为英文接收动态反馈
你的好友是一位健身爱好者。前段日子，他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。
他会有一份计划消耗的卡路里表，其中 calories[i] 给出了你的这位好友在第 i 天需要消耗的卡路里总量。
为了更好地评估这份计划，对于卡路里表中的每一天，你都需要计算他 「这一天以及之后的连续几天」 （共 k 天）内消耗的总卡路里 T：

  • 如果 T < lower，那么这份计划相对糟糕，并失去 1 分；
  • 如果 T > upper，那么这份计划相对优秀，并获得 1 分；
  • 否则，这份计划普普通通，分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。
注意：总分可能是负数。

  1. /**
  2.  * @param {number[]} calories
  3.  * @param {number} k
  4.  * @param {number} lower
  5.  * @param {number} upper
  6.  * @return {number}
  7.  */
  8. var dietPlanPerformance = function(calories, k, lower, upper) {
  9.   let t = 0, r = 0, ans = 0;
  10.   while (r < calories.length && r < k) {
  11.     t += calories[r++];
  12.   }
  13.   const update = (t) => {
  14.     if (t > upper) {
  15.       return 1;
  16.     }
  17.     if (t < lower) {
  18.       return -1;
  19.     }
  20.     return 0;
  21.   };
  22.   ans += update(t);
  23.   while (r < calories.length) {
  24.     t += calories[r];
  25.     t -= calories[r - k];
  26.     ans += update(t);
  27.     r++;
  28.   }
  29.   return ans;
  30. };

【计数】1456. 定长子串中元音的最大数目

  1. /**
  2.  * @param {string} s
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var maxVowels = function(s, k) {
  7.   const dict = new Set(['a', 'e', 'i', 'o', 'u']);
  8.   let t = 0;
  9.   for (let i = 0; i < k; i++) {
  10.     t += dict.has(s.charAt(i)) ? 1 : 0;
  11.   }
  12.   let ans = t;
  13.   for (let i = k; i < s.length; i++) {
  14.     t += dict.has(s.charAt(i)) ? 1 : 0;
  15.     t -= dict.has(s.charAt(i - k)) ? 1 : 0;
  16.     ans = Math.max(ans, t);
  17.   }
  18.   return ans;
  19. };

【平均数】643. 子数组最大平均数 I

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var findMaxAverage = function(nums, k) {
  7.   let ans = 0, t = 0;
  8.   for (let i = 0; i< k; i++) {
  9.     t+= nums[i];
  10.   }
  11.   ans = t;
  12.   for (let i = k; i < nums.length; i++) {
  13.     t = t + nums[i] - nums[i-k];
  14.     ans = Math.max(ans, t);
  15.   }
  16.   return ans/k;
  17. };

【有条件计算】1052. 爱生气的书店老板

  1. // 写法一：定长式简单写法，不死脑细胞
  2. /**
  3.  * @param {number[]} customers
  4.  * @param {number[]} grumpy
  5.  * @param {number} minutes
  6.  * @return {number}
  7.  */
  8. var maxSatisfied = function(customers, grumpy, minutes) {
  9.   let ans = 0, t = 0, base = 0;
  10.   for (let i = 0; i < minutes; i++) {
  11.     t += customers[i] * grumpy[i];
  12.     base += customers[i] * (1 - grumpy[i]);
  13.   }
  14.   ans = t;
  15.   for (let i = minutes; i < customers.length; i++) {
  16.     base += customers[i] * (1 - grumpy[i]);
  17.     t += customers[i] * grumpy[i];
  18.     t -= customers[i - minutes] * grumpy[i-minutes]
  19.     ans = Math.max(ans, t);
  20.   }
  21.   return base + ans;
  22. };
  24. /**
  25.  * @param {number[]} customers
  26.  * @param {number[]} grumpy
  27.  * @param {number} minutes
  28.  * @return {number}
  29.  */
  30. var maxSatisfied = function(customers, grumpy, minutes) {
  31.   let sum = 0, start = 0, base = 0, maxDiff = 0;
  32.   // 求的结果为最多满意的客户，由于可以作弊变脸色，所以结果可以分成两个部分，一个是不受变脸色影响的结果，这个部分的特点是grumpy[i] 为0；
  33.   // 受影响是grumpy[i] === 1的部分，而minutes为窗口大小，故只需要计算grumpy[i] === 1 时的customers在窗口中的最大窗口值。
  34.   for (let i = 0; i < customers.length; i++) {
  35.     // 不受影响的部分的前缀和计算
  36.     base += customers[i] * ( 1 - grumpy[i]);
  37.     // 受影响的部分的前缀和计算
  38.     sum  += customers[i] * grumpy[i];
  39.     // 计算影响因子的大小，求最大值。最大值一般产生在窗口扩展时
  40.     maxDiff = Math.max(maxDiff, sum);
  41.     // 窗口大小满足，为固定窗口，所以不用循环，只判断一次。
  42.     if (i - start + 1 === minutes) {
  43.       // 窗口右移，计算区间和
  44.       sum -= customers[start] * grumpy[start];
  45.       // 如果需要计算最小值，可以在在次计算。发生在窗口收缩
  46.       // 窗口右移
  47.       start++;
  48.     }
  49.   }
  50.   // 两部分之和。
  51.   return base + maxDiff;
  52. };
  55. // 写法三：不定长的方式来写。
  56. /**
  57.  * @param {number[]} customers
  58.  * @param {number[]} grumpy
  59.  * @param {number} minutes
  60.  * @return {number}
  61.  */
  62. var maxSatisfied = function(customers, grumpy, minutes) {
  63.   let l = 0, r = 0, ans = 0, t = 0, base = 0;
  64.   while (r < customers.length) {
  65.     base += customers[r] * (1 - grumpy[r]);
  66.     t += customers[r] * grumpy[r];
  67.     r++;
  68.     while (r - l > minutes) {
  69.       t -= customers[l] * grumpy[l];
  70.       l++;
  71.     }
  72.     ans = Math.max(ans, t);
  73.   }
  74.   return base + ans;
  75. };

【左右两端】1423. 可获得的最大点数

  1. /**
  2.  * @param {number[]} cardPoints
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var maxScore = function(cardPoints, k) {
  7.   let ans = 0, t = 0, len = cardPoints.length;
  8.   for (let i = len - k ; i <len; i++) {
  9.     t += cardPoints[i];
  10.   }
  11.   ans = t;
  12.   for (let i = 0; i < k; i++) {
  13.     t += cardPoints[i] - cardPoints[len - k + i];
  14.     ans = Math.max(ans, t);
  15.   }
  16.   return ans;
  17. };

【排列】438. 找到字符串中所有字母异位词

  1. /**
  2.  * @param {string} s
  3.  * @param {string} p
  4.  * @return {number[]}
  5.  */
  6. var findAnagrams = function(s, p) {
  7.   let ct = new Array(26).fill(0), ans=[], base = 'a'.charCodeAt(0);
  8.   const t = new Array(26).fill(0);
  9.   for (let r = 0; r < p.length; r++) {
  10.     ct[p.charCodeAt(r) - base]++;
  11.     t[s.charCodeAt(r) - base]++;
  12.   }
  13.   const isValidWindow = () => {
  14.     for (let i = 0; i < ct.length; i++) {
  15.       if (ct[i] === 0) continue;
  16.       if (ct[i] !== t[i]) return false;
  17.     }
  18.     return true;
  19.   };
  21.   const updateAns = (pos) => {
  22.     if (isValidWindow()) {
  23.       ans.push(pos);
  24.     }
  25.   };
  27.   updateAns(0);
  29.   for (let r = p.length; r < s.length; r++) {
  30.     t[s.charCodeAt(r) - base]++;
  31.     t[s.charCodeAt(r - p.length) - base]--;
  32.     updateAns(r - p.length + 1);
  33.   }
  34.   return ans;
  35. };

【排列】567. 字符串的排列

这题可以看作是上面的题目 438的简化，只需要判断是否有，而不用全记录， 直接基于上题的模板套路修改下结果更新。

  1. /**
  2.  * @param {string} s1
  3.  * @param {string} s2
  4.  * @return {boolean}
  5.  */
  6. var checkInclusion = function(s1, s2) {
  7.   let s = s2, p = s1;
  8.   let ct = new Array(26).fill(0), base = 'a'.charCodeAt(0);
  9.   const t = new Array(26).fill(0);
  10.   for (let r = 0; r < p.length; r++) {
  11.     ct[p.charCodeAt(r) - base]++;
  12.     t[s.charCodeAt(r) - base]++;
  13.   }
  14.   const isValidWindow = () => {
  15.     for (let i = 0; i < ct.length; i++) {
  16.       if (ct[i] === 0) continue;
  17.       if (ct[i] !== t[i]) return false;
  18.     }
  19.     return true;
  20.   };
  21.   if (isValidWindow()) {
  22.     return true;
  23.   }
  24.   for (let r = p.length; r < s.length; r++) {
  25.     t[s.charCodeAt(r) - base]++;
  26.     t[s.charCodeAt(r - p.length) - base]--;
  27.     if (isValidWindow()) {
  28.       return true;
  29.     }
  30.   }
  31.   return false;
  32. };

【交换/中等】1151. 最少交换次数来组合所有的 1

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

思路：

目标是，是将所有的11集中在一起，这个时候的窗口长度为真个串中1的个数len，在这种情况下，要使交换次数最少，即为其中的0的数量最少。

于是将原问题转换为求长度为len的窗口中，0最少的窗口，而答案即为窗口内0的数量。

由于只有0、1两种数字，个数的计算等价与求和，故计算窗口的sum值，最后再以窗口长度-sum即可。

  1. /**
  2.  * @param {number[]} data
  3.  * @return {number}
  4.  */
  5. var minSwaps = function(data) {
  6.   // 最少交换，存在一个长度为 |1的个数| 的窗口，计数其中的1的个数为最大，反过来这个区间中的0的个数即为最少交换次数。
  7.   let t = data.filter(p => p === 1).length;
  8.   let r = 0, s = 0, ans = 0;
  9.   while (r < t) {
  10.     s += data[r++];
  11.   }
  12.   ans = s;
  13.   while (r < data.length) {
  14.     s += data[r];
  15.     s -= data[r-t];
  16.     ans = Math.max(ans, s);
  17.     r++;
  18.   }
  19.   return t - ans;
  20. };