Study Notes

Appearance

滑动窗口 ​

灵神视频精讲：滑动窗口

题单 ​

题目代码备注
209. 长度最小的子数组代码最短
3. 无重复字符的最长子串代码最长
713. 乘积小于 K 的子数组代码方案数
3090. 每个字符最多出现两次的最长子字符串代码*课后作业
2958. 最多 K 个重复元素的最长子数组代码*课后作业
2730. 找到最长的半重复子字符串代码*课后作业
2779. 数组的最大美丽值代码*课后作业
1004. 最大连续 1 的个数 III代码*课后作业
2962. 统计最大元素出现至少 K 次的子数组代码*课后作业
2302. 统计得分小于 K 的子数组数目代码*课后作业
1658. 将 x 减到 0 的最小操作数代码*课后作业
1234. 替换子串得到平衡字符串代码*课后作业
3795. 不同元素和至少为 K 的最短子数组长度代码*课后作业
76. 最小覆盖子串代码*课后作业

例题 ​

209. 长度最小的子数组 ​

  • 核心思路：同向双指针（滑动窗口）。
  • 模板：先移动右指针 r，当满足条件时（sum >= target），尝试移动左指针 l 缩小窗口，并更新答案。
  • 注意：打日志调试很重要。
js
/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function (target, nums) {
    //明显不能从两端相向，应该是同向
    //if -> while打日志发现的；
    //滑窗模版
    let l = 0, r = 0, ans = Infinity, n = nums.length,sum = 0;
    if (n < 2) {
        if (nums[0] >= target) return 1;
    }

    while (r < n) {
        sum += nums[r];
        while(sum >= target) {
            console.log('l=',l,'r=',r,sum)
            ans = Math.min(ans,r - l +1)
            sum -= nums[l];
            l++;
        }
        r++;
        
    }
    return ans === Infinity ? 0 : ans;

};

3. 无重复字符的最长子串 ​

  • 数据结构：使用 Map 记录字符频率（或下标）。
  • 思路：
    • 右指针 r 向右移动，将字符加入窗口。
    • 如果窗口内有重复字符（mp.get(c) > 1），左指针 l 向右移动直到无重复。
    • 每次移动右指针后更新最大长度 ans。
  • 语法：?? 空值合并运算符（见附录）。
js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    //涉及到数组or哈希map，js的哈希map没学过的:new Map(),set,get
    //滑动窗口（同向双指针）：答案更新一般靠近中后

    //知识点 x？？y，问号左边为null或undefined就用y；
    
    //如果没有就右边指针往右移动，如果有就左指针往右，要记录最长的长度而且无重复map[r];while 操作左指针可以去重
    let ans = 0, l = 0;
    const n = s.length;

    let mp = new Map();
    for (let r = 0; r < n; r++) {
        let c = s[r];
        // mp.set('c', 1);
        mp.set(c, (mp.get(c) ?? 0) + 1)
        while (mp.get(c) > 1) {
            mp.set(s[l], (mp.get(s[l]) ?? 0) - 1)
            l++;
        }
        // console.log(l, mp.get(s[l]), r, mp.get(s[r]))
        ans = Math.max(ans, r - l + 1)
    }
    return ans;
};

713. 乘积小于 K 的子数组 ​

  • 特征：窗口越大乘积越大（越不合法），窗口越小乘积越小（越合法）。
  • 思路：
    • 右指针扩大窗口，累乘。
    • 当乘积 >= k 时，左指针缩小窗口。
    • 关键：每次右指针固定时，合法子数组个数为 r - l + 1（避免双重循环）。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numSubarrayProductLessThanK = function (nums, k) {
    //由于连续，所以不能排序，大概率也不是相向双指针，看样例
    //判断答案就一个sum+if，关键是怎么遍历所有情况，先考虑滑动窗口，由于子数组越长，乘积越大，越不能满足题目要求；反之，子数组越短，乘积越小，越能满足题目要求。有这种性质的题目，可以用滑动窗口解决。


    //为什么滑动窗口可以遍历所有连续子数组？
    //固定右边，移动左边就可以用r-l+1来避免双重循环了
    let ans = 0, n = nums.length, ji = 1, l = 0;
    for (let r = 0; r < n; r++) {
        ji *= nums[r];
        while (ji >= k) {
            //写缩小逻辑
            ji /= nums[l];
            l++;
        }
        if (ji < k && l <= r) ans += r - l + 1;


    }
    return ans;
};

作业 ​

3090. 每个字符最多出现两次的最长子字符串 ​

  • 思路：同向双指针。右指针扩大窗口，Map 统计频次，当频次 > 2 时左指针缩小窗口。
  • 注意：Map 的 set 和 get 语法。
js
/**
 * @param {string} s
 * @return {number}
 */
var maximumLengthSubstring = function(s) {
    //要求最长，越大越合法，所以同向双指针，也就是滑动窗口
    //纯小写的话，直接插入map就行了
    //思路：右指针从左开始扩大窗口，while循环缩小不合法的窗口，更新答案
    let l = 0, n = s.length, ans = 0;
    let mp = new Map();
    for(let r = 0; r < n; r++){
        mp.set(s[r],(mp.get(s[r])??0)+1);

        while(mp.get(s[r])>2){
            mp.set(s[l],mp.get(s[l])-1);
            l++;
            // console.log(mp.get(s[r]),l,r)
        }
        ans = Math.max(ans,r - l +1)
    }
    return ans;
};

2958. 最多 K 个重复元素的最长子数组 ​

同上题，改两个变量名就行了

2730. 找到最长的半重复子字符串 ​

  • 思路：统计相邻相同字符的对数 cnt。
  • 缩小条件：当 cnt > 1 时，移动左指针，如果左指针移出的是一对重复字符，则 cnt--。
js
/**
 * @param {string} s
 * @return {number}
 */
var longestSemiRepetitiveSubstring = function (s) {

    //要求最长，越大越合法，所以同向双指针，也就是滑动窗口
    //为什么要r从1开始？：经验？
    let l = 0, n = s.length, cnt = 0, ans = 0;
    if (n === 1) return 1;
    for (let r = 1; r < n; r++) {
        if (s[r] === s[r - 1]) cnt++;
        if (n === 2 && cnt === 1) cnt = 0;
        while (cnt > 1) {
            if (s[l] === s[l + 1]) cnt--;

            l++;
            // console.log(mp.get(s[r]),l,r)

        }
        if (cnt <= 1) ans = Math.max(ans, r - l + 1);

    }
    return ans;
};

2779. 数组的最大美丽值 ​

  • 思路：
    • 排序：因为是选子序列（或理解为元素值调整），顺序不影响，先排序。
    • 转换：题目等价于找一个最长的子数组，使得 max - min <= 2*k。
    • 滑窗：nums[r] - nums[l] > 2*k 时缩小窗口。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function (nums, k) {
    //由于可以操作任意次，那可以排序
    nums.sort((a, b) => a - b);
    //越大越合法，滑动窗口
    //数学推导，带范围的可以在图上画好区间，发现要求的就是最多交集个数，也就是左边+k大于等于右边-k，那就用到反面条件来缩小窗口
    let ans = 0, l = 0, n = nums.length;
    for (let r = 0; r < n; r++) {

        // console.log('r - l', nums[r] - nums[l])
        while (nums[r] - nums[l] > 2 * k) {
            l++;
        }
        //合法的时候记录最大的
        ans = Math.max(ans, r - l + 1);
        // console.log(l, r, ans)
    }
    return ans;
};

1004. 最大连续 1 的个数 III ​

  • 思路：统计窗口内 0 的个数。
  • 条件：当 0 的个数 > k 时，缩小窗口。
  • 感悟：很有成就感的一题，多总结题目特征和调试经验。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestOnes = function (nums, k) {
    //越大越合法，所以考虑相向双指针
    //要统计频次，哈希数组
    //缩小窗口的条件：0的次数大于k
    //在哪里打印？哪里变了？l,r,mp
    let l = 0, ans = 0, n = nums.length;
    let mp = new Map();
    for (let r = 0; r < n; r++) {
        mp.set(nums[r], (mp.get(nums[r]) ?? 0) + 1)
        while (mp.get(0) > k) {
            mp.set(nums[l], (mp.get(nums[r]) ?? 0) - 1);
            l++;
            // console.log('进循环了')
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
};

2962. 统计最大元素出现至少 K 次的子数组 ​

  • 思路：
    • 统计最大元素出现的次数 cnt。
    • 当 cnt === k 时，窗口合法。
    • 关键：当窗口 [l, r] 合法时，l 左边的所有位置作为左端点也都合法，所以 ans += l（注意这里代码逻辑是 while 循环结束后 l 指向的位置）。
    • 这里的代码逻辑是：当窗口内最大元素个数达到 k 时，尝试移动左指针，直到个数不足 k。每次移动左指针，说明找到了一个合法的左边界。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function (nums, k) {
    //越大越合法，滑动窗口
    //难点：不知道缩小窗口的条件，不知道答案怎么计算
    //把方法和思路记住吧：在刚好合法的时候缩小到刚好不合法，那么此时l左边至少有一个max element，然后r指针指着一个，那（0，l-1）都是答案
    let ans = 0, l = 0, cnt = 0, maxelement = Math.max(...nums);
    for (let r = 0; r < nums.length; r++) {
        if (nums[r] === maxelement) cnt++;
        while (cnt === k) {
            if (nums[l] === maxelement) cnt--;
            l++;
        }
        ans += l;
    }
    return ans;
};

2302. 统计得分小于 K 的子数组数目 困难 ​

  • 特征：越短越合法。
  • 思路：
    • 维护窗口和 sum。
    • 当 sum * (r - l + 1) >= k 时（不合法），缩小窗口。
    • 合法时，以 r 为右端点的合法子数组个数为 r - l + 1。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var countSubarrays = function (nums, k) {
    //容易想到，长度可以关联成r - l + 1;
    //要统计和那就移动右指针，貌似跟昨天的题很像，左指针往左的，不对
    //越小越合法？但是相向双指针就无法求和，还是滑窗？
    //暴力？一个一个加，< k/r-l+1，ans++,数据量太大肯定超时
    //看答案：越短越合法某一子数组合法那它的子数组也就都合法，所以只需要找一个缩小窗口的条件，找一下左右指针跟答案的关系
    //正常判断缩小条件，发现答案规律就是刚好缩小到合法之后的区间值

    let ans = 0, l = 0, sum = 0;
    for (let r = 0; r < nums.length; r++) {
        sum += nums[r];
        while (sum * (r - l + 1) >= k) {
            sum -= nums[l];
            l++;
        }
        // console.log(l,r)
        ans += r - l + 1;
    }
    return ans;
};

1658. 将 x 减到 0 的最小操作数 ​

  • 逆向思维：
    • 原问题：找两端子数组和为 x。
    • 转化后：找中间最长连续子数组，和为 sum - x。
  • 思路：标准滑动窗口找和为 target 的最长子数组。
js
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minOperations = function (nums, x) {
    //逆向思考，发现其实是，首尾相接，找最短数组让它之和🟰x，返回窗口长度
    //按照例题找出答案的规律试试，两个数组拼在一块，但是就是无法排除在数组中间部分而且长度很小的情况
    //越小越合法？靠在两边的滑动窗口？？？？
    //贪心？

    //原来是这样做的，在这个答案部分逆向：我们可以这样转化问题：
    // 设数组总和为 sum
    // 如果我们从两端取的总和为 x，那么中间剩余部分的和就是 sum - x
    // 问题转化为：找到最长的连续子数组，其和等于 sum - x
    // 那么最小操作数 = 总长度 -  .最长. 中间子数组长度
    // 这个转化很巧妙，因为找中间连续子数组比直接找两端子数组更容易！
    let ans = -1, l = 0;
    let sum = nums.reduce((a, b) => { return a + b }), tmp = sum - x, tmpsum = 0, n = nums.length;
    //     // 正确使用 reduce 计算数组总和（必须传回调函数）
    // const sum = nums.reduce((accumulator, currentValue) => {
    //   // accumulator：累计值（上一轮的结果），currentValue：当前遍历的元素
    //   return accumulator + currentValue;
    // }, 0); // 第二个参数 0 是初始值（推荐必传，避免空数组报错）

    for (let r = 0; r < nums.length; r++) {
        tmpsum += nums[r];

        while (tmpsum > tmp) {
            tmpsum -= nums[l];
            l++;
            // console.log(tmpsum, l, r)
        }
        if (tmpsum === tmp) {
            // console.log('循环外', l, r);
            ans = Math.max(ans, r - l + 1);
        }


    }
    return ans === -1 ? -1 : n - ans;
};

1234. 替换子串得到平衡字符串 困难 ​

  • 逆向思维：
    • 不要想“改什么”，要想“不改什么（保留什么）”。
    • 目标：保留下来的外部字符，每种字符数量都 <= n/4。
    • 这样剩下的空缺就可以通过替换子串来补齐。
  • 思路：统计频次，寻找最短子串，使得移除该子串后，剩余字符频次满足条件。
js
/**
 * @param {string} s
 * @return {number}
 */
var balancedString = function (s) {
    //又是越小越合法，但是，中间的变量明显不好搞，估计不是从窗口的反面考虑
    //越小越合法，还要连续子串，还要统计频次？？，不会做
    // 正确的逆向思路是：
    // 我们不要去想“要改什么”，而是去想“不改什么”。
    // 目标：最终整个字符串里，每个字符（Q, W, E, R）的数量都恰好是 n / 4。
    // 约束：我们只能通过替换一个连续子串来改变字符。这意味着，我们无法改变这个子串之外的字符。
    // 关键推论：既然子串之外的字符不能改，那么这些“外部”字符的数量，必须已经满足要求——也就是每种字符的个数都 不能超过 n / 4。
    // 为什么？ 因为如果外面某个字符（比如 Q）已经超过了 n / 4 个（比如有 3 个，而 n / 4=2），那这个 Q 就太多了。我们只能改子串里的字符，动不了外面的 Q，所以永远无法把多出来的 Q 减少，最终字符串一定不平衡。
    // 反过来说：只要外面每种字符的数量都不超过 n / 4，那么我们就可以通过巧妙地替换子串里的字符，来补齐那些数量不足的字符，让整个字符串达成平衡。
    // 所以，问题神奇地转化为了：寻找一个最短的连续子串，使得去掉这个子串后（即这个子串之外的字符），每种字符的数量都不超过 n / 4。

    //统计频次，寻找一个小点的窗口让外部都小于n/4，缩小窗口条件也就是外部各个频次都小于这个值
    const cnt = { Q: 0, W: 0, E: 0, R: 0 };
    const n = s.length, m = n / 4;
    let ans = n, l = 0;
    for (let x of s) {
        // cnt.x++;///x是值，不能这样写了
        cnt[x]++;
    }

    if (cnt.Q === m && cnt.E === m && cnt.W === m && cnt.R === m) return 0;
    for (let r = 0; r < n; r++) {
        cnt[s[r]]--;
        while (cnt.Q <= m && cnt.E <= m && cnt.W <= m && cnt.R <= m) {
            ans = Math.min(ans, r - l + 1)
            // console.log('in while', l, r)
            cnt[s[l]]++;
            l++;

        }

    }
    return ans === n ? 0 : ans;
};

3795. 不同元素和至少为 K 的最短子数组长度 ​

  • 思路：
    • 统计“有效元素”（频次为 1 的元素）的和。
    • 移动右指针，更新 Map 和 Sum。
    • 移动左指针缩小窗口时，注意 Sum 的更新时机（只有当元素频次减为 0 时，才从 Sum 中减去，这取决于题目对“不同元素和”的定义）。
js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minLength = function (nums, k) {
    //越小越合法，统计用于计算的频次最多1，他们之和要大于等于k，答案是这样的最小窗口长度
    //标志变量来标记是否使用呗？
    let ans = 1e5, l = 0, n = nums.length, sum = 0;
    let map = new Map();
    for (let r = 0; r < n; r++) {
        map.set(nums[r], (map.get(nums[r]) ?? 0) + 1);
        if (map.get(nums[r]) === 1) sum += nums[r];
        while (sum >= k && l <= r) {
            ans = Math.min(r - l + 1, ans)
            map.set(nums[l], (map.get(nums[l]) ?? 0) - 1);

            //主要是这一行，缩小sum的时机，因为统计nums【r】的时候，加入 ,c , c, b, r指针;两个c，算和是算了一次但是计频次记了两次，下次就是这种情况可以打印一下频次来排错
            if (map.get(nums[l]) === 0) sum -= nums[l];
            l++;
            // console.log('in while', l, r, sum, ans)
        }
    }
    return ans === 1e5 ? -1 : ans;

};

76. 最小覆盖子串 困难 ​

  • 核心：如何判断“涵盖”？
  • 技巧：使用 Array(128) 和 codePointAt(0) 代替 Map 提高性能。
  • 思路：
    • 统计 t 中字符频次。
    • 移动右指针，统计窗口内字符频次。
    • check 函数检查是否涵盖。
    • 涵盖时，尝试移动左指针缩小窗口，并记录最小长度。
js
function isCovered(cntS, cntT) {
    //优先判断false的情况
    for (let i = 'A'.codePointAt(0); i <= 'Z'.codePointAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false;
        }
    }
    for (let i = 'a'.codePointAt(0); i <= 'z'.codePointAt(0); i++) {
        if (cntS[i] < cntT[i]) {
            return false;
        }
    }
    return true;
}

var minWindow = function(s, t) {
    const cntS = Array(128).fill(0); 
    const cntT = Array(128).fill(0);
    for (const c of t) {
        cntT[c.codePointAt(0)]++;
    }

    const m = s.length;
    let ansLeft = -1, ansRight = m,left = 0;

    for (let right = 0; right < m; right++) {
        cntS[s[right].codePointAt(0)]++; // 右端点字母移入子串
        while (isCovered(cntS, cntT)) { // 涵盖
            if (right - left < ansRight - ansLeft) { // 找到更短的子串
                ansLeft = left; // 记录此时的左右端点
                ansRight = right;
            }
            cntS[s[left].codePointAt(0)]--; // 左端点字母移出子串
            left++;
        }
    }

    return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1);
};

附录 ​

1. JavaScript Map 基础 ​

在刷题中，推荐使用 Map 而不是普通对象，因为 Map 在频繁增删键值对时性能更好，且键可以是任意类型。

常用操作：

javascript
const map = new Map();
// 增/改
map.set('key', 1);
// 查
map.get('key'); // 返回 1
map.has('key'); // 返回 true
// 删
map.delete('key');
// 默认值技巧
let val = map.get(key) ?? 0; // 如果不存在则为 0

2. 空值合并运算符 (??) ​

?? 专门用于处理 null 和 undefined。

javascript
// 刷题常用写法：获取 map 值，如果不存在则默认为 0
mp.set(c, (mp.get(c) ?? 0) + 1);

3. 对象属性的引号 ​

  • 不加引号：属性名符合标识符规则（字母开头，无特殊字符）。
    js
    const count = { Q: 0, W: 0 };
  • 动态访问：必须使用 []。
    js
    const key = 'Q';
count[key]++; // 正确
// count.key++ // 错误：这会找名为 "key" 的属性

4. 字符编码操作 ​

对于 ASCII 字符统计（如大小写字母），使用数组比 Map 更快。

  • codePointAt(0)：获取字符的 Unicode 码点（ASCII 码）。
    js
    'A'.codePointAt(0); // 65
  • Array(128).fill(0)：创建一个长度 128 的数组并初始化为 0，足以覆盖所有 ASCII 字符。