📚 plmblog

Appearance

03-滑动窗口

📅 发表于 2026/04/02
🔄 更新于 2026/08/05
👁️ — 次访问
📝 3101 字
⏳ 10 分钟

总结 ​

一些概念 ​

小心

异位词

  • abc和bca为异位词
  • 直接判断counter是否相等即可。

覆盖子串

  • abcd为覆盖abc的串。
  • 需要判断字符数量 大于等于。

题目总结 ​

1-003-无重复字符的最长子串

题目

  • 求解字符串s中，连续最长不重复子串的长度。

暴力法

  • 依次遍历每个字符作为起始，向后求解，计算当前子串长度。

滑动窗口左右指针法

  • 左右指针定义窗口子串[l,r]，遍历r，求解每个窗口长度r-l+1 。
  • 为保证窗口内无重复字符
    • 若s[r]出现过，左侧指针需要往前移动，到s[r]出现位置的下一个位置。
    • l只能往前，需要取max，避免连续重复字符导致回退。
  • 记录每个字符出现位置。
2-438-找到字符串中所有字母异位词

题目

  • 给长字符串s和短字符串p，求解s中p的所有字母异位子串，固定窗口大小。

暴力法

  • 遍历s每个字符，作为窗口起始值 左指针，判断窗口子串和p是否异位词。 (Key)

左右指针统计次数法

  • 异位词：使用Counter统计p和窗口子串的字符次数。
  • 遍历右指针
    • 右指针进入，计算窗口大小，旧左指针出去。
    • 计算窗口值。
3-560-和为K的子数组

题目

  • 给一个nums数组和一个目标求和值k，计算和为k的连续子数组数量。

前缀和哈希解法

  • 记录前缀和 出现次数
  • 遍历数组，计算当前前缀和，减去K，计算需要前缀和
  • 从Hash中，提取需要前缀和的数量。
4-239-滑动窗口最大值

题目

  • 给定nums数组，和滑动窗口大小k。依次输出每个窗口内的最大值。

双端单调队列滑动窗口队头最大值法

  • 滑动窗口遍历right边界，计算left边界。
  • 双端队列，保证单调递增。队首>队尾，队首作为窗口最大值，存储下标。
  • 队首过期出队：超出left边界。
  • 新队尾入队：保证为队列最小值；若旧队尾小于当前值，则需循环出队。
5-076-最小覆盖子串

题目

  • 给字符串s和t，计算s中，覆盖t中所有字符的最短子串

子串覆盖

  • 某字符覆盖：窗口字符次数 >= t中字符次数

滑动窗口右扩展左收缩找最短覆盖

  • 遍历右指针，右指针进入窗口。
  • 当前窗口满足：
    • 更新窗口大小
    • 左指针循环收缩，找最小窗口。窗口不满足则停止收缩。
    • 右指针扩张
  • 当前窗口不满足：右指针扩张。

题目 ​

1-003-无重复字符的最长子串 ​

1-003-无重复字符的最长子串

leetcode-003

  • 输入：字符串s，可能有多个相同不同的字符
  • 输出：字符串里最长不重复子串的长度。
  • 示例：abcdbcd -> abcd -> 4；aaaa -> a -> 1

暴力遍历各字符作为起始的最长子串长度 ​

暴力遍历各字符作为起始的最长子串长度
  • 遍历每个字符，依次计算其作为起始字符的最大长度。
  • 依次往后找，设置出现字符集合，若某字符已出现过，则停止。
python
def lengthOfLongestSubstring_force_loop(self, s: str) -> int:
    """ 暴力遍历，从每个字符开始，往后查找
    """
    if not s:
        return 0
    n = len(s)
    max_length = 1
    for i in range(n):
      	# 从i往后找，已出现字符集合，s[i] 已出现
        cur_sets = set()
        cur_sets.add(s[i])  
        j = i + 1
        # 从i往后找，若出现，则停止寻找
        while j < n and s[j] not in cur_sets:  
            cur_sets.add(s[j])
            j += 1
        # 更新最大长度
        max_length = max(max_length, len(cur_sets))  
    return max_length

左右指针滑动窗口计算长度法 ​

左右指针滑动窗口计算长度法

左右指针滑动窗口思想

  • 初始化左右指针l=r=0，ch2pos={} 记录ch出现位置
  • 固定l 遍历r ：确定窗口 [l,r] 更新长度
    • 当前字符s[r]，保证窗口[l, r]无重复字符
    • 若s[r]已出现过 (s[r] in ch2pos)，
      • 则更新l到旧s[r]出现位置的下一个位置：l=ch2pos[ch]+1
      • 但l不能往回走，需取max： l=max(ch2pos[ch] + 1, l)
    • 更新s[r]位置为r，ch2pos[ch]=r
    • 当前窗口： [l, r]，计算长度=r-l+1，更新max_len
    • r 往前走： r+= 1

左指针不能往回走

  • 比如abba例子，l=2, r=3, 但若直接下一个位置，则l=1，往回走，导致重复
python
def lengthOfLongestSubstring_leftright_sliding_window(self, s: str) -> int:
    if not s:
        return 0
    n = len(s)

    # 左右双指针
    l = r = 0
    # 记录字符出现的位置
    ch2pos = {}
    max_len = 0

    # 右指针往前走，左指针看情况往前走，每次循环计算一个窗口 [l,r]
    while r < n:  
        # 当前窗口最右侧的字符
        ch = s[r]
        if s[r] in ch2pos:  
            # 需要保证 [l, r] 之间无重复字符
            # 当前字符已出现过，l指针需往前移动到出现字符的下一个位置，但是不能往回走。
            # 比如abba这个例子，l=2, r=3, 但若是直接下一个位置，则l=1，往回走，导致重复
            l = max(ch2pos[ch] + 1, l)  
        # 更新位置
        ch2pos[ch] = r
        # 当前窗口长度
        cur_len = r - l + 1
        max_len = max(max_len, cur_len)
        # 右指针继续往前走
        r += 1
    return max_len

2-438-找到字符串中所有字母异位词 ​

2-438-找到字符串中所有字母异位词

leetcode-438

  • 输入：长字符串s，短字符串p。
  • 输出：s中 所有p的异位词的子串位置。

相关题目

暴力穷举判断异位词 ​

暴力穷举判断异位词
  • 依次遍历s中每个字符，作为窗口起始值。判断当前窗口和p是否是异位词。
  • 异位词判断：排序后 生成字符串key，判断 key相同即可。
  • 会超时。
python
def findAnagrams_force_loop(self, s: str, p: str) -> List[int]:
    res = []
    if not s or not p:
        return []

    # p的key和窗口大小
    pkey = "".join(sorted(p))
    window_size = len(p)
    for i in range(len(s)):
        j = i + window_size  
        if j > len(s):
            break
        # 当前窗口值
        subs = s[i:j]
        subs_key = "".join(sorted(subs))
        if pkey == subs_key:  
            res.append(i)
    return res

滑动窗口左右指针统计次数法 ​

滑动窗口左右指针统计次数法

窗口异位词判断

  • 使用Counter()类，直接判断 cnt_p == cnt_s，即字符出现次数 是否相等。

核心思想

  • 统计p字符串、滑动窗口字符出现次数。
  • 遍历右指针 做循环
    • 右指针字符进入，新元素+1。
    • left<0 ：窗口大小不足，继续循环
    • left>0：窗口溢出，左指针字符 出去，旧元素-1。
    • 计算当前窗口内容：cnt_p == cnt_s

滑动窗口三字经

  • 进：s_count[新元素] += 1
  • 出：if 长度超标: s_count[旧元素] -= 1
  • 算：if s_count == p_count: 记录答案
python
def findAnagrams_leftright_window(self, s: str, p: str) -> List[int]:
    res = []
    if not s or not p or len(s) < len(p):
        return res
    # 直接统计p字符串以及窗口中的字符出现次数
    cnt_p = Counter(p)   
    cnt_s = Counter()  

    for right, ch in enumerate(s):
        # 右侧字符+1
        cnt_s[ch] += 1
        # 窗口左侧位置
        left = right - len(p) + 1
        if left < 0:
            # 窗口大小不足
            continue
        if left > 0:
            # 窗口起始位置>0，上一轮的左侧位置减1
            pre_left = left - 1
            cnt_s[s[pre_left]] -= 1
        # 直接判断两个counter是否相似，自动忽视值为0的项
        if cnt_p == cnt_s:  
            res.append(left)
    return res

3-560-和为K的子数组 ​

3-560-和为K的子数组

leetcode-560

  • 输入：数组nums，整数和k
  • 输出：和为k的连续子数组 数量
相似题

前缀和加补数求数量 ​

前缀和加补数求数量

前缀和、出现次数

  • 前缀和 pre[i]：数组元素位置0到i的求和

    s[i]=pre[i]=∑j=0inums[j]

  • 哈希计数：统计前缀和具体值的出现次数

核心思想

  • 定义累计前缀和current_sum、前缀和出现次数count、初始化count[0]=1
  • 遍历每个元素
    • 计算含当前位置元素的前缀和pre[i]
    • 计算当前位置的补数：补数 = 前缀和 - 求和k
    • 如果补数存在，则：次数 += 补数次数
    • 计算完当前节点后，最后再更新 当前前缀和 出现次数

注意

  • 并非单调递增，不能用 滑动窗口。

示例

  • [1, 2, 3, 4, 5]，K=7，正确应该是 [3, 4] 子数组
  • 前缀和：[1, 3, 6, 10, 15]
  • 补数前缀和：[-6, -3, -1, 3, 8]
  • 补数前缀和3 出现1次，则次数+1。把[1,2]去掉，剩下[3,4]，则和为K=7
python
def subarraySum(self, nums: List[int], k: int) -> int:
    """
    前缀和+Hash记录次数
    """
    if not nums:
        return 0

    # 累计前缀求和
    current_sum = 0
    # 前缀出现次数
    count = defaultdict(int)
    # 必须初始化前缀和0为1
    # 因为 1, 2, 3。若是k=3，到1 2的时候，need_sum=0，正好1,2算一个
    count[0] = 1

    res = 0
    for num in nums:
        # 当前前缀和
        current_sum += num
        # 当前位置所需的前缀
        need_sum = current_sum - k
        if need_sum in count:
            # 累加之前的所有统计值
            res += count[need_sum]  
        # 更新当前前缀和
        count[current_sum] += 1
    return res

4-239-滑动窗口最大值 ​

4-239-滑动窗口最大值

leetcode-239

  • 输入：数组nums，固定滑动窗口 大小k。从左到右移动，每次只能看k个数字。
  • 输出：所有滑动窗口内的最大值组成的列表。

双端单调队列窗口队首最值法 ​

双端单调队列窗口队首最值法

双端队列

  • 队列存储下标，方便判断队首过期
  • 队列单调递增：队首 最大值 > 队尾 最小值
  • 每个窗口取当前队首，作为其最大值。

滑动窗口核心思想

  • 遍历右指针 做循环
    • 计算当前滑动窗口[l, r]的 left边界
    • 处理队列值
      • 过期队首 循环出队：不在窗口内，queue[0] < l
      • 小队尾 循环出队：保证nums[r]入队后 为最小值，
        • 即nums[queue[-1]] < nums[r]时，队尾一直出队
    • 当前元素nums[r] 入队
    • 若当前窗口[l-r] 满足大小，则取队首值为当前窗口最大值
python
def maxSlidingWindow_queue(self, nums: List[int], k: int) -> List[int]:
    """ 使用单调队列：保持先进先出单调递增，当前值超过队首最大值，则队列清空后再入队；当前值小于队尾值，则直接入队。队首超期，也出队
    """
    res = []
    if not nums or len(nums) < k or k <= 0:
        return res 

    # 队列
    queue = deque(maxlen=k)  

    # 循环遍历每个元素，作为右侧窗口值
    n = len(nums)

    for right in range(n):
        # 滑动窗口左侧值
        left = right - k + 1

        # 1. 队首过期出队，不在滑动窗口里
        if len(queue) > 0 and queue[0] < left:  
            queue.popleft()

        # 2. 队尾检查，保证队尾元素大于当前值
        while len(queue) > 0 and nums[queue[-1]] < nums[right]:  
            # 队尾出队
            queue.pop()

        # 3. 当前元素入队
        queue.append(right)

        # 4. 计算滑动窗口值
        if left >= 0:
            res.append(nums[queue[0]])  

    return res

5-076-最小覆盖子串 ​

5-076-最小覆盖子串

leetcode-076

  • 输入：字符串s和t
  • 输出：s中，覆盖 t中所有字符的最短子串
  • 示例：s=BECODEBANC，t=ABC，最小子串=BANC

滑动窗口右扩展左收缩 ​

滑动窗口右扩展左收缩方法

子串覆盖判断

  • 字符hash，各字符分别判断。
  • 需要：窗口字符次数 >= 目标字符次数。大于等于很重要，并不只是等于。

滑动窗口右扩展左收缩

  • 右指针：先一直往右走，直到当前窗口包含最短子串。
  • 左指针：后一直往右走，直到当前窗口不包含最短子串。

核心链路

  • 循环遍历右指针，右指针进入窗口
  • 当前窗口不满足
    • 右指针+1，右指针扩展
  • 当前窗口满足
    • 计算更新窗口大小
    • 循环 左指针收缩，寻找最小窗口
      • 当前窗口满足：更新窗口大小；左指针继续收缩。
      • 当前窗口不满足：break掉
    • 右指针+1，右指针扩展
python
def minWindow_lrwindow(self, s: str, t: str) -> str:
    """滑动窗口，右指针扩充，左指针收缩
    """
    if not s or not t or len(s) < len(t):
        return ""

    # 字符串计数
    cnt_w = defaultdict(int)
    cnt_t = defaultdict(int)

    for ch in t:
        cnt_t[ch] += 1

    # 左右指针
    l = r = 0

    def match_substr():
        match_all = True
        for ch, cnt in cnt_t.items():
            # 窗口内的cnt需要大于等于目标cnt
            if cnt_w[ch] < cnt:  
                match_all = False
                break
        return match_all

    res = ""
    while r < len(s):
        # 右指针进入窗口
        cnt_w[s[r]] += 1

        # 判断当前窗口是否满足
        match_all = match_substr()

        if match_all:
            # 当前窗口满足子串，计算更新窗口
            if not res or r-l+1 < len(res):
                res = s[l:r+1]

            # 左指针向右收缩，寻找最小子串
            while l+1 <= r:  
                cnt_w[s[l]] -= 1
                l += 1
                match_all = match_substr()
                if match_all:
                    if r-l+1 < len(res):
                        res = s[l:r+1]
                else: 
                    break
            # 右指针继续往前走
            r += 1
        else:
            # 当前窗口不满足，右指针扩展
            r += 1

    return res
总访客数：— · 总访问量：—
PLM's Blog @ 2016 - 2026