江月迟迟的个人知识库

外观

滑动窗口模块 ​

作者:江月迟迟
发表于:2024-12-20
字数统计:1901 字
预计阅读7分钟

滑动窗口是双指针的方法，有left指针和right指针。常用于求解最短/最长/方案数问题。

最短 ​

模板 ​

js
function minWindow(xxx, xxx) {
    // 使用滑动窗口解决，优先收敛
    // 初始化变量，辅助变量，指标

    // 开始滑动窗口逻辑
    for(; right < s.length; right++) {
        // 处理当前节点

        // 大胆收敛left指针
        while(rc === c) {
            // 记录答案
            
            // 收敛left指针：1. 消除left指针相关的影响，2. 收敛
            
        }
    }
    return ans
}

题目 ​

209. 长度最小的子数组

js
var minSubArrayLen = function(target, nums) {
    // 滑动窗口，找到长度最小的滑动窗口，right指针谨慎++，left指针大胆++，就是优先收敛长度，优先收敛left指针
    let left = 0, right = 0, ans = Infinity, sum = 0
    for(; right < nums.length; right++) {
        // 使用for循环，在left指针不可++的时候，才right++
        
        // 处理当前节点
        sum += nums[right]
        // left指针大胆收敛
        while(left <= right && sum >= target) {
            ans = Math.min(ans, right - left + 1)
            sum -= nums[left]
            left++
        }
        
    }
    return ans === Infinity ? 0 : ans
};

76. 最小覆盖子串

js
function minWindow(s, t) {
    // 使用滑动窗口解决，优先收敛
    // ans记录答案、rc是required count，用来记录有多少个字符需要满足要求。c用来记录当前有多少个字符满足要求
    let left = 0, right = 0, ans = '', rc = 0, c = 0
    const smap = new Map()
    const tmap = new Map()
    
    // 记录t的每个字符需要多少个
    for(let char of t) tmap.set(char, (tmap.get(char) || 0) + 1)
    rc = tmap.size

    // 开始滑动窗口逻辑
    for(; right < s.length; right++) {
        // 处理当前节点
        const node = s[right]

        // 加进去
        smap.set(node, (smap.get(node) || 0) + 1)

        // 达到条件，更改c
        if(tmap.has(node) && smap.get(node) === tmap.get(node)) c++

        // 大胆收敛left指针
        while(rc === c) {
            // 记录答案 1. 初始化的时候ans === 0，2. 有了答案之后ans只需要取最短就行
            if(right - left + 1 < ans.length || ans.length === 0) {
                ans = s.slice(left, right+1)
            }
            // 收敛left指针：1. 消除left指针相关的影响，2. 收敛
            const node1 = s[left]
            smap.set(node1, (smap.get(node1) || 0) - 1)
            if(tmap.has(node1) && smap.get(node1) < tmap.get(node1)) c--
            left++
        }
    }
    return ans
}

最长 ​

模板 ​

js
var maxSubarrayLength = function(nums, k) {
    
    // 大胆扩张right，小心收敛left
    for(; right < nums.length; right++) {
        // 处理节点

   
        // 小心收敛left就是，不满足不收敛条件（题目的反向条件），就不收敛
        while() {

        }
        // 记录答案
        
    }
    return ans
};

题目 ​

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

js
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // 优先扩张right指针，小心收敛Left指针
    let left = 0, right = 0, ans = 0
    const set = new Set()
    while(right < s.length) {
        const node = s[right]
        if(!set.has(node)) {
            set.add(node)
            ans = Math.max(ans, set.size)
            right++
            continue
        }
        set.delete(s[left])
        left++
    }
    return ans
};

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let left = 0, ans = 0
    const set = new Set()
    for(let right = 0; right < s.length; right++) {
        // 一直删，直到刚好没left
        while(set.has(s[right])) {
            set.delete(s[left])
            left++
        }
        set.add(s[right])
        ans = Math.max(ans, set.size)

    }
    return ans
};

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

js
var maxSubarrayLength = function(nums, k) {
    let left = 0, right = 0, ans = 0
    const map = new Map()
    // 大胆扩张right，小心收敛left
    while(right < nums.length) {
        const node = nums[right]
        const count = map.get(node) || 0
        if(count < k) {
            map.set(node, (map.get(node) || 0) + 1)
            ans = Math.max(ans, right - left + 1)
            right++
            continue
        }
        // 小心收敛left
        const node1 = nums[left]
        map.set(node1, map.get(node1) - 1)
        left++
    }
    return ans
};


var maxSubarrayLength = function(nums, k) {
    let left = 0, right = 0, ans = 0
    const map = new Map()
    // 大胆扩张right，小心收敛left
    while(right < nums.length) {
        const node = nums[right]
        const count = ( map.get(node) || 0) + 1
        if(count <= k) {
            map.set(node, (map.get(node) || 0) + 1)
            ans = Math.max(ans, right - left + 1)
            right++
            continue
        }
        // 小心收敛left
        const node1 = nums[left]
        map.set(node1, map.get(node1) - 1)
        left++
    }
    return ans
};


var maxSubarrayLength = function(nums, k) {
    let left = 0, right = 0, ans = 0
    const map = new Map()
    // 大胆扩张right，小心收敛left
    for(; right < nums.length; right++) {
        // 处理节点
        const node = nums[right]
        map.set(node, (map.get(node) || 0) + 1)
       
        // 小心收敛left就是，不满足不收敛条件（题目的反向条件），就不收敛
        while(map.get(node) > k) {
            map.set(nums[left], (map.get(nums[left]) || 0) - 1)
            left++
        }
        ans = Math.max(ans, right - left + 1)
    }
    return ans
};

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

js
/**
 * @param {string} s
 * @return {number}
 */
var longestSemiRepetitiveSubstring = function(s) {
    let left = 0, right = 0, c = 0, ans = 0, rc = 1, pn = []

    for(; right < s.length; right++) {
        const node = s[right]
        if(right > 0 && node === s[right-1]) {
            c++
            pn.push(right)
        }

        while(c > rc) {
            while(pn.length && left !== pn[0]) {
                left++
            }
            c--
            pn.shift()
        }
        ans = Math.max(ans, right - left + 1)

    }
    return ans
};

var longestSemiRepetitiveSubstring = function(s) {
    let left = 0, right = 0, c = 0, ans = 0, rc = 1, pn = []

    while(right < s.length) {
        // 处理节点
        if(right > 0 && s[right] === s[right-1]) {
            c++
            pn.push(right)
        }
        // 小心收敛left指针
        while(c > rc) {
            while(left !== pn[0]) {
                left++
            }
            c--
            pn.shift()
        }

        ans = Math.max(ans, right - left + 1)

        // 大胆扩张right指针
        right++
        
    }
    return ans
};

2779. 数组的最大美丽值

js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumBeauty = function(nums, k) {
    nums.sort((a,b) => a-b)
    let ans = 0, left = 0, right = 0
    for(; right < nums.length; right++) {
        const node = nums[right]
        while(node - nums[left] > k * 2) left++
        ans = Math.max(ans, right - left + 1)
    }
    return ans
};

方案数 ​

模板 ​

题目 ​

713. 乘积小于 K 的子数组

js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
//  前缀和
var numSubarrayProductLessThanK = function(nums, k) {
    if (k <= 1) return 0; // 特殊情况处理

    const logK = Math.log(k); // k 的对数
    const prefixLog = Array(nums.length + 1).fill(0); // 前缀对数和
    let count = 0;

    // 构建前缀对数和
    for (let i = 0; i < nums.length; i++) {
        prefixLog[i + 1] = prefixLog[i] + Math.log(nums[i]);
    }

    // 遍历所有子数组
    for (let i = 0; i < nums.length; i++) {
        // 二分查找右边界
        let left = i + 1, right = prefixLog.length, mid;
        while (left <= right) {
            mid = Math.floor((left + right) / 2);
            if (prefixLog[mid] - prefixLog[i] + 1e-10 < logK) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 四舍五入处理浮点误差
        count += Math.round(left - i - 1); 
    }

    return count;
};

// 滑动窗口
var numSubarrayProductLessThanK = function(nums, k) {
    if(k <= 1) return 0
    let left = 0, right = 0, product = 1, ans = 0

    // 方案数不同于求最小或者求最大，只是去记录每一个满足条件的结果
    for(; right < nums.length; right++) {
        // 处理节点
        product *= nums[right]
        while(product >= k) {
            product /= nums[left]
            left++
        }
        ans += right - left + 1
    }

    return ans

}

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

js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
//  前缀和
var countSubarrays = function(nums, k) {
    nums.unshift(0)
    let ans = 0
    const prefixSum = Array(nums.length).fill(0)
    for(let i = 0; i < nums.length-1; i++) {
        prefixSum[i+1] = prefixSum[i] + nums[i+1]
    }
    // 还是只能二分查找
    for(let i = 0; i < nums.length; i++) {
        let left = 0, right = i, mid
        while(left <= right) {
            mid = (left + right) / 2 | 0
            if((prefixSum[i] - prefixSum[mid]) * (i - mid) >= k) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        ans += i - left
    }
    return ans
};


var countSubarrays = function(nums, k) {
    let left = 0, ans = 0;
    const prefixSum = Array(nums.length + 1).fill(0);

    // 计算前缀和
    for (let i = 0; i < nums.length; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }

    // 使用滑动窗口计算符合条件的子数组数目
    for (let right = 1; right <= nums.length; right++) {
        // 当前窗口的分数
        let count = (prefixSum[right] - prefixSum[left]) * (right - left);

        // 收缩窗口直到分数小于 k
        while (count >= k) {
            left++;
            count = (prefixSum[right] - prefixSum[left]) * (right - left);
        }

        // 累加以当前 `right` 为结尾的满足条件的子数组数量
        ans += right - left;
    }

    return ans;
};



// 滑动窗口
var countSubarrays1 = function(nums, k) {
    let left = 0, right = 0, ans = 0, sum = 0
    
    for(; right < nums.length; right++) {
        sum += nums[right]
        while(sum * (right - left + 1) >= k) {
            sum -= nums[left++]
        }
        ans += right - left + 1
    }
    return ans
};