滑动窗口算法

滑动窗口算法介绍

算法简介

在数组 / 字符串上维护一个固定或可变长度的窗口，通过滑动和缩放窗口，动态维护区间内的最优解

• 滑动：窗口整体向一个方向移动，通常是向右
• 缩放：窗口长度可变时，可以通过移动左指针缩小窗口，或移动右指针扩大窗口
  滑动窗口本质上是双指针的一种应用，可以理解为用两个指针维护一个区间，动态调整区间范围以满足题目要求

应用场景

滑动窗口常用于查找满足某些条件的连续子区间，能将嵌套循环优化为单循环，大幅降低时间复杂度。常见题型包括：

• 固定长度窗口：窗口大小固定，通常用于统计或查找长度为 k 的区间性质
• 可变长度窗口：窗口大小不固定，常用于查找满足条件的最长/最短区间

---

代码实践

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

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

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

思路
维护一个字符窗口，left与right来标识这个窗口，每次right右移表示扩大窗口，也就是拿进一个字符，这里利用ASCII码范围0-127这个性质维护一个数组，记录每个字符出现的次数，根据不重复再进行窗口的选择

代码实现

#define MAX(a, b) ((a) > (b) ? (a) : (b))
int lengthOfLongestSubstring(char* s){
    int cnt[128];
    memset(cnt, 0, sizeof(cnt));
    int left = 0, ans = 0;
    for(int right = 0; s[right]; right++){
        char tmp=s[right];
        cnt[tmp]++;
        // 注意这里是while而不是if，要缩小到窗口内满足不重复条件
        while(cnt[tmp]>1){
            // 先移除左边端点的cnt，再left--，窗口移动
            cnt[s[left]]--;
            left++;
        }
        ans = MAX(ans, right-left+1);
    }
    return ans;
}

---

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

LeetCode 438. 找到字符串中所有字母异位词

问题描述
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词的子串，返回这些子串的起始索引,不考虑答案输出的顺序

思路
本题解题思路有两种：

• 定长窗口：
  p的长度为n，所以维护一个长度也为n的窗口，之后统计这个窗口中每种字符出现的次数，与p中每种字符出现次数比较，如果相同，则是异位词，反之如果不是，需要左侧端点字符滑出窗口
• 不定长窗口：
  枚举子串 s' 的右端点，如果发现 s' 中某一种字母的出现次数大于 p 中该字母的出现次数，则右移 s' 的左端点（缩小窗口）。如果发现 s' 的长度等于 p 的长度，则说明 s' 中每种字母的出现次数都等于 p 中对应字母的出现次数，即 s' 是 p 的异位词

代码实现

方法一：定长窗口

int* findAnagrams(char* s, char* p, int* returnSize) {
    // 统计p串的字符信息
    int cnt_p[26];
    memset(cnt_p, 0, sizeof(cnt_p));
    int n=0;
    for(;p[n];n++){
        cnt_p[p[n] - 'a']++;
    }

    int* res = (int*)malloc(sizeof(int)*strlen(s));
    *returnSize=0;
    int cnt_s[26];
    memset(cnt_s,0,sizeof(cnt_s));
    for(int right=0;s[right];right++){
        // 这里的int left=right-n+1;很巧妙
        // 既可以使之后满足窗口n条件
        // 还因为right++从而left自动右移
        int left=right-n+1;
        cnt_s[s[right]-'a']++;
        if(left<0) continue;
        if(memcmp(cnt_s,cnt_p,sizeof(cnt_s))==0){
            res[(*returnSize)++]=left;
        }
        cnt_s[s[left]-'a']--;
    }
    return res;
}

方法二：不定长窗口

int* findAnagrams(char* s, char* p, int* returnSize) {
    // 统计 p 的每种字母的出现次数
    int cnt[26] = {};
    int n = 0;
    for (; p[n]; n++) {
        cnt[p[n] - 'a']++;
    }
    
    int* ans = malloc(strlen(s) * sizeof(int));
    *returnSize = 0;
    int left = 0;

    for (int right = 0; s[right]; right++) {
        int c = s[right] - 'a';
        cnt[c]--; // 右端点字母进入窗口
        while (cnt[c] < 0) { // 字母 c 太多了
            cnt[s[left] - 'a']++; // 左端点字母离开窗口
            left++;
        }
        if (right - left + 1 == n) { // s' 和 p 的每种字母的出现次数都相同
            ans[(*returnSize)++] = left; // s' 左端点下标加入答案
        }
    }
    return ans;
}

---

3. 长度最小的子数组

LeetCode 209. 长度最小的子数组

问题描述
给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其总和大于等于 target 的长度最小的子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0

思路
不定长滑动窗口实现，只要窗口内大于等于target，就判定一次长度，之后left向右移，一直到right到达数组最后

代码实现

#define MIN(a, b) ((a) < (b) ? (a) : (b))

int minSubArrayLen(int target, int* nums, int numsSize) {
    int left = 0;
    int sum = 0;
    int ans = INT_MAX;

    for (int right = 0; right < numsSize; right++) {
        sum += nums[right];
        // 收缩窗口：只要 sum >= target，就尝试缩小
        while (sum >= target) {
            ans = MIN(ans, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return (ans == INT_MAX) ? 0 : ans;
}

---

4. 乘积小于 K 的子数组

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

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

思路
维护不定长窗口，当前窗口内满足条件时，对于固定的 right，有 right-left+1 个合法的左端点，如果不满足条件，一直移动左边界直到满足条件
本题重点在于这句话：
对于固定的 right，有 right-left+1 个合法的左端点

代码实现

int numSubarrayProductLessThanK(int* nums, int numsSize, int k) {
    if (k <= 1) {
        return 0;
    }
    int ans = 0, prod = 1, left = 0;
    for (int right = 0; right < numsSize; right++) {
        prod *= nums[right];
        while (prod >= k) { // 不满足要求
            prod /= nums[left];
            left++; // 缩小窗口
        }
        // 对于固定的 right，有 right-left+1 个合法的左端点
        ans += right - left + 1;
    }
    return ans;
}

注意：
问：如果不特判 k ≤ 1，代码要怎么改？

答：如果 k ≤ 1，那么代码中的 prod >= k 恒为真。可以额外判断 left ≤ right 避免下标越界，即内层循环条件改成 left <= right && prod >= k