分享｜不定长滑动窗口

14 小时前

发布于河南

双指针 C C++Java Python3 算法和数据结构

不定长滑动窗口

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。

核心思想

不定长滑动窗口通常用于寻找“满足某个条件的最长/最短子序列（包含子串，子数组）”。其操作逻辑可以概括为：

右指针（r）主动扩张：不断向右移动，将新元素加入窗口，直到窗口内的内容不再满足条件（或达到某种临界状态）。
左指针（l）被动收缩：一旦条件不满足，就开始移动左指针，剔除元素，直到窗口重新满足条件。
更新答案：在上述过程中，记录窗口长度的最大值或最小值。

不定长滑动窗口的单调性法则

建议先大概过一遍遍本部分内容，把下面的题目学习一遍之后再回来深度理解。

1. 越长越合法

特征： 如果一个窗口满足条件，那么比它更长的窗口（通常是包含它的窗口）极大概率也满足条件，或者我们要找的是满足条件的极限长度。

典型题目： “最长子串...”、“包含至少 K 个...”、“所有字符出现次数不小于 K”。
核心逻辑： 1. 右指针 r 狂奔，直到窗口变得合法。
1. 左指针 l 开始收缩，直到窗口刚刚不合法。
更新位置： 通常在 while 循环外，因为 while 结束代表收缩到了“最长合法”的临界点。

代码套路：

for r in range(n):
    # 进窗逻辑
    while 窗口已经合法:
        # 记录/更新
        l += 1

2. 越短越合法

特征： 这是你最近练习最多的类型。如果一个窗口满足条件，那么它缩短后可能依然合法，我们要找的是满足条件的物理极小值。

典型题目： “最短子串...”、“最小覆盖子串”、“替换后平衡的最短子串”。
核心逻辑：
1. 右指针 r 狂奔，直到窗口满足要求。
2. 左指针 l 立即开始压榨，直到窗口不再满足要求。
更新位置： 必须在 while 循环内。因为每缩短一步，都可能产生一个新的“最短记录”。

代码套路：

for r in range(n):
    # 进窗逻辑
    while 窗口满足要求:
        ans = min(ans, r - l + 1) # 趁合法，赶紧记
        # 出窗逻辑
        l += 1

3. 文档对比表

维度	越长越合法 (求最长/最大)	越短越合法 (求最短/最小)
窗口性质	条件通常是 “上限”（如：不同字符不超过 K）	条件通常是 “下限”（如：总和至少为 K）
While 意义	纠错（把不合法的变合法）	压榨（把合法的变更短）
更新 ans	`ans = max(ans, r - l + 1)`	`ans = min(ans, r - l + 1)`
更新位置	`while` 循环外	`while` 循环内
零值特判	通常不需要	经常需要（因为最短可能是 0）

4. 为什么会有这种差异？（深度思考）

越长越合法 (求最长/最大)：当你发现窗口非法时（比如字符种类太多了），你移动左指针是为了回到合法状态。一旦合法，这个位置就是当前 r 下能伸展的最远距离。
越短越合法 (求最短/最小)：当你发现窗口合法时，你的第一反应应该是：“能不能更短点？”。所以你会不断移动左指针，直到它刚好不合法为止。这个过程中的每一个点都可能是答案。

模板

Cpp

#include <bits/stdc++.h>
using namespace std;

int slidingWindow(string s) {
    // 1. 初始化
    unordered_map<char, int> window;
    int left = 0, right = 0;
    int ans = 0; // 根据要求初始化，求最大通常为0，求最小通常为INT_MAX

    // 2. 右指针移动
    while (right < s.size()) {
        // 【进】：将新元素加入窗口
        char c = s[right];
        right++; // 右移窗口
        
        // --- 进行窗口内数据的一系列更新 ---
        window[c]++;

        // 3. 判断左侧窗口是否要收缩
        // 求最长：通常 while (窗口非法)
        // 求最短：通常 while (窗口合法)
        while (/* 窗口需要收缩的条件 */) {
            // 【出】：将左侧元素移出窗口
            char d = s[left];
            left++; // 左移窗口
            
            // --- 进行窗口内数据的一系列更新 ---
            if (window[d] == 1) {
                window.erase(d);
            } else {
                window[d]--;
            }
        }
        
        // 4. 更新答案
        ans = max(ans, right - left); // 这里的 right 已经自增过了，所以不用 +1
    }
    return ans;
}

Python

def slidingWindow(s):
    # 1. 初始化
    window = {} # 或 set(), list()，根据题目需求选择
    ans = 0 # 结果（最大长度或最小长度）
    left = 0
    
    # 2. 右指针移动
    for right in range(len(s)):
        # 【进】：将新元素 s[right] 加入窗口
        char_r = s[right]
        # 更新窗口内的相关状态（如计数、求和等）
        window[char_r] = window.get(char_r, 0) + 1
        
        # 3. 判断是否需要收缩左指针
        # 【最长子串】：通常 while 条件是“窗口非法”
        # 【最短子串】：通常 while 条件是“窗口合法”
        while (窗口不符合题目要求): 
            # 【出】：将 s[left] 移出窗口
            char_l = s[left]
            # 更新窗口内的相关状态
            window[char_l] -= 1
            if window[char_l] == 0:
                del window[char_l]
            left += 1 # 左指针右移
            
        # 4. 更新答案
        # 注意：如果是求最长，在这更新；如果是求最短，可能在 while 内部更新
        ans = max(ans, right - left + 1)
        
    return ans

越短越合法/求最长/最大

题目一

来源：力扣3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

思路

求最长的经典模板题，套模板即可，因为要保证窗口中不含重复字符，使用 $se t$ 和 $ma p / d i c t$ 均可高效判断。

优化一

用 $ma p / d i c t$ 记录字符最后出现的位置，窗口每向后拓展一个字符，就判断此字符前一个位置和窗口左边界 $l$ 的位置，如果前一个位置在左边界之前，则窗口内无重复字符，反之则重复，更新左边界位置到拓展的字符的前一个位置+1处，刚好把前一个位置卡在左边界之前，满足无重复字符条件。注意每次更新更新当前字符的最新位置。

代码实现

Python原思路

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = defaultdict(int)

        ans, l = 0, 0
        for r in range(len(s)):
            d[s[r]] += 1

            while len(d) < r - l + 1:
                d[s[l]] -= 1
                if d[s[l]] == 0:
                    del d[s[l]]
                l += 1

            ans = max(ans, r - l + 1)

        return ans

Python优化一

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        d = {}
        ans, l = 0, 0

        for r in range(len(s)):
            if s[r] in d:
                l = max(l, d[s[r]] + 1)

            d[s[r]] = r
            ans = max(ans, r - l + 1)

        return ans

题目二

来源：力扣3634. 使数组平衡的最少移除数目

给你一个整数数组 nums 和一个整数 k。

如果一个数组的最大元素的值至多是其最小元素的 k 倍，则该数组被称为是平衡的。

你可以从 nums 中移除任意数量的元素，但不能使其变为空数组。

返回为了使剩余数组平衡，需要移除的元素的最小数量。

**注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

思路

本题看似求移除最小数量，逆向思维求最大剩余数量更简单，符合滑动窗口使用条件

由于我们只关心剩余元素的最小值和最大值，不关心元素的顺序，所以可以先从小到大排序，方便后续计算。

排序后，枚举最大值 $m x = n u m s [i]$ ，那么最小值 $mn = n u m s [l e f t]$ 必须满足

mn \cdot k \geq m x

由于已经排序，所以题目自然而然的转换成一个经典的不定长滑动窗口，保证窗口新进元素小于最小元素（左边界处元素）的 $k$ 倍即可。

还可以做个小优化，排序前先取数组中最大值和最小值，判断是否符合 $mn \cdot k \geq m x$ ，如果符合直接返回 $0$ 即可

代码实现

Python

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        min_val, max_val = min(nums), max(nums)
        if max_val <= k * min_val:
            return 0

        nums.sort()
        res = l = 0
        for r, x in enumerate(nums):
            while x > k * nums[l]:
                l += 1

            res = max(res, r - l + 1)

        return len(nums) - res

越长越合法/求最短/最小

题目一

来源：力扣209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

思路

求最短的经典模板题，套模板即可，窗口向后扩增中，判断窗口内 $s u m$ 是否大于等于 $t a r g e t$ ，如果大于，开始向后移动左边界，直到 $s u m < t a r g e t$ ，因为要求最短，在左边界向后移动过程中，可能产生更符合要求的更短窗口，所以此处更新答案。

代码有两种写法，在 while 循环内更新答案 和 在while 循环结束后更新答案，两种写法没有本质区别。

目标类型	典型 while 条件	推荐更新位置	为什么？
求最长 (Max)	`while (窗口非法)`	循环外	`while` 的作用是“纠错”，纠完错后的窗口才是合法的，此时更新最稳。
求最短 (Min)	`while (窗口合法)`	循环内	`while` 的作用是“压榨”，每缩小一点都要看看是否还合法，以此逼近最小值。

所以以后的求最短的题目中，都优先在循环内更新答案，便于理解。

代码实现

Python写法一：在 while 循环内更新答案

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        s = l = 0
        ans = inf
        for r, x in enumerate(nums):
            s += x
            while s >= target:
                ans = min(ans, r - l + 1)
                s -= nums[l]
                l += 1

        return 0 if ans == inf else ans

Python写法二：在 while 循环结束后更新答案

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        s = l = 0
        ans = inf
        for r, x in enumerate(nums):
            s += x
            while s - nums[l] >= target:
                s -= nums[l]
                l += 1

            if s >= target:
                ans = min(ans, r - l + 1)

        return 0 if ans == inf else ans

题目二

来源：力扣3795. 不同元素和至少为 K 的最短子数组长度

给你一个整数数组 nums 和一个整数 k。

返回一个 子数组 的最小长度，使得该子数组中出现的不同值之和（每个值只计算一次）至少为 k。如果不存在这样的子数组，则返回 -1。

子数组 是数组中一个连续的非空元素序列。

思路

本题其实就是上一题加一个条件，窗口内相同的值之加一次，用哈希表统计窗口内元素出现次数即可，进入窗口时如果之前窗口内没有此元素，则加进 sum ，左边界向后移动把元素抛出窗口时，如果抛出后没有这个元素值，则从 sum 中减去。

代码实现

Python

class Solution:
    def minLength(self, nums: List[int], k: int) -> int:
        ans = inf
        s = l = 0
        d = defaultdict(int)
        for r, x in enumerate(nums):
            # 可以改成 "if d[x] == 0:"，减少一次判断
            if x not in d:
                s += x
            d[x] += 1

            while s >= k:
                ans = min(ans, r - l + 1)
                t = nums[l]
                l += 1
                d[t] -= 1
                if d[t] == 0:
                    s -= t
                    del d[t]  #这句可以删掉，减少一次操作，但是大数据量下占用内存 

        return -1 if ans == inf else ans

题目三

来源：力扣1234. 替换子串得到平衡字符串

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。

假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。

给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。

你可以用和「待替换子串」长度相同的任何其他字符串来完成替换。

请返回待替换子串的最小可能长度。

如果原字符串自身就是一个平衡字符串，则返回 0。

思路

本质还是滑动窗口，题目要求在字符串中替换一个子串以保证每个字符都恰好出现 $n /4$ 次，由于我们替换的子串内可以是任意字符，我们只需保证窗口外每个字符出现次数都小于等于 $n /4$ 即可（这样就能通过替换窗口内字符使每个字符都符合要求，如果窗口外有一个字符数量大于 $n /4$ 则不可能完成要求）。

基本思路是先统计出每个字符总体出现次数（推荐使用哈希表统计），这个次数减去窗口内出现的次数就是窗口外出现的次数，然后 $w hi l e (窗口合法)$ 更新答案即可。

注意统计出每个字符总体出现次数是先判断一下初始是否满足条件。

代码实现

Python

class Solution:
    def balancedString(self, s: str) -> int:
        cnt = Counter(s)
        ans, l, m = inf, 0, len(s) // 4
        if all(cnt[x] <= m for x in "QWER"):
            return 0

        for r, c in enumerate(s):
            cnt[c] -= 1
            while all(cnt[x] <= m for x in "QWER"):
                ans = min(ans, r - l + 1)
                cnt[s[l]] += 1
                l += 1

        return ans

求子数组个数

越短越合法

一般要写 ans += right - left + 1。

内层循环结束后，[left,right] 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 [left,right]，还有 [left+1,right],[left+2,right],…,[right,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 left,left+1,left+2,…,right 的所有子数组都是满足要求的，这一共有 right−left+1 个。

题目一

来源：力扣

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

思路

注意数据范围 $n u m s [i] \geq 1$ ，所以乘积不可能小于 $1$ 。因此，当 $k \leq 1$ 时，没有这样的子数组，直接返回 $0$ 。

由于子数组越长，乘积越大，越不能满足题目要求；反之，子数组越短，乘积越小，越能满足题目要求。有这种性质的题目，可以用滑动窗口解决。

枚举子数组右端点 $r i g h t$ ，如果发现子数组不满足要求，就缩小窗口，也就是增大左端点 $l e f t$ 。

Q：为什么加 $r i g h t - l e f t + 1$ ？

A：内层循环结束后， $[l e f t, r i g h t]$ 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 $[l e f t, r i g h t]$ ，还有 $[l e f t + 1, r i g h t], [l e f t + 2, r i g h t], \dots, [r i g h t, r i g h t]$ 都是满足要求的。也就是说，当右端点固定在 $r i g h t$ 时，左端点在 $l e f t, l e f t + 1, l e f t + 2, \dots, r i g h t$ 的所有子数组都是满足要求的，一共有 $r i g h t - l e f t + 1$ 个，加到答案中。

Q：如果不特判 $k \leq 1$ ，代码要怎么改？

A：如果 $k \leq 1$ ，那么代码中的 $p ro d >= k$ 恒为真。可以额外判断 $l e f t \leq r i g h t$ 避免下标越界，即内层循环条件改成 $l e f t <= r i g h t$ && $p ro d >= k$ 。

代码实现

Python

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0

        ans = l = 0
        f = 1
        for r, x in enumerate(nums):
            f *= x
            while f >= k:
                f //= nums[l]
                l += 1

            ans += r - l + 1

        return ans

越长越合法

一般要写 ans += left。

内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个。

我们关注的是 left−1 的合法性，而不是 left。

题目一

来源：力扣1358. 包含所有三种字符的子字符串数目

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都至少出现过一次的子字符串数目。

思路

经典的窗口越长越容易合法，窗口先向后拓展，当窗口合法时，移动左边界，直至不合法，但是移动之前的窗口都合法，例如 $l$ 从 $0 - > l e f t$ ，中间的合法情况有 $l e f t$ 个所以结果 $an s + = l e f t$ 。

代码实现

Python

class Solution:
    def numberOfSubstrings(self, s: str) -> int:
        d = defaultdict(int)
        ans = l = 0
        for r, c in enumerate(s):
            d[c] += 1
            while d["a"] and d["b"] and d["c"]:
                d[s[l]] -= 1
                l += 1

            ans += l

        return ans

恰好型/三指针滑动窗口

例如，要计算有多少个元素和恰好等于 $k$ 的子数组，可以把问题变成：

计算有多少个元素和 $\geq k$ 的子数组。

计算有多少个元素和 $> k$ ，也就是 $\geq k + 1$ 的子数组。

答案就是元素和 $\geq k$ 的子数组个数，减去元素和 $\geq k + 1$ 的子数组个数。这里把 $>$ 转换成 $\geq$ ，从而可以把滑窗逻辑封装成一个函数 $so l v e$ ，然后用 $so l v e (k) - so l v e (k + 1)$ 计算，无需编写两份滑窗代码。

总结：「恰好」可以拆分成两个「至少」，也就是两个大于等于 $g o a l$ 个数的滑窗问题。

注：也可以把问题变成 $\leq k$ 减去 $\leq k - 1$ ，即两个「至多」。可根据题目选择合适的变形方式。

注：也可以把两个滑动窗口合并起来，维护同一个右端点 $r i g h t$ 和两个左端点 $l e f t 1$ 和 $l e f t 2$ ，这种写法也叫做三指针滑动窗口。

题目一

来源：力扣930. 和相同的二元子数组

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的非空子数组。

子数组 是数组的一段连续部分。

思路

经典的恰好型滑动窗口，计算和为 $g o a l$ 的子数组，可以简化为小于等于 $g o a l$ 的个数减去小于 $g o a l$ 的个数（小于等于 $g o a l + 1$ 的个数），即分别计算两个越短越合法的窗口，最后再相减。

当然也可以转化为两个越长越合法的窗口或者使用上面提到的三指针滑动窗口。

代码实现

Python写法一：差分双窗口（越短越合法）

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        def atMost(k: int) -> int:
            if k < 0:
                return 0

            res = l = s = 0
            for r, x in enumerate(nums):
                s += x
                while s > k:
                    s -= nums[l]
                    l += 1

                res += r - l + 1

            return res

        return atMost(goal) - atMost(goal - 1)

Python写法二：三指针滑动窗口

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        s1 = s2 = l1 = l2 = ans = 0
        for r, x in enumerate(nums):
            s1 += x
            s2 += x

            while l1 <= r and s1 >= goal:
                s1 -= nums[l1]
                l1 += 1

            while l2 <= r and s2 > goal:
                s2 -= nums[l2]
                l2 += 1

            ans += l1 - l2

        return ans