双指针，滑动窗口

滑动窗口与双指针

一、定长滑动窗口

核心特征

在长度为 n 的字符串/数组中，寻找长度为 k 且满足特定极值条件的子数组

复杂度对比

  • 暴力解法：遍历所有子数组 ⇒
  • 滑动窗口：动态维护窗口 ⇒

实现要点

  1. 窗口维护机制

    • 使用双指针（左右指针）或枚举右端点维护左端点
    • 始终保持窗口长度
    • 增量更新：处理新进入元素和被移出元素

  2. 标准操作流程

    1
    2
    3
    4
    5
    while 右指针未越界:
        新元素入窗 → 更新指标值
        if 窗口大小达到 k:
            更新全局极值
        	旧元素出窗 → 修正指标值

  3. 例题 1456. 定长子串中元音的最大数目

    给定字符串 s 和整数 k，返回长度为 k 的子串中元音字母的最大数量（元音字母：a, e, i, o, u）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // 灵茶山艾府答案
    class Solution {
    public:
        int maxVowels(string s, int k) {
            int ans = 0, vowel = 0;
            for (int i = 0; i < s.length(); i++) {
                // 1. 进入窗口
                if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') 			{
                    vowel++;
                }
                if (i < k - 1) { // 窗口大小不足 k
                    continue;
                }
                // 2. 更新答案
                ans = max(ans, vowel);
                // 3. 离开窗口
                char out = s[i - k + 1];
                if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
                    vowel--;
                }
            }
            return ans;
        }
    };

二、不定长滑动窗口

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

  • 求 最长/最短 子数组：需要维护一 最长/最短 的合法窗口 => 不断更新全局最值

  • 求子数组个数

    • 越长子数组越合法
    • 越短子数组越合法
    • 恰好型滑动窗口

2.1.求最长/最大（至多)

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

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。

我们枚举右端点，维护左端点

​ 子数组右端点：right

​ 子数组左端点：left

维护ans：ans=max(ans,right-left+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumLengthSubstring(string s) {
        int left=0,ans=0;
        unordered_map<char,int> count_map;
        for(int i=0;i<s.size();i++)
        {
            count_map[s[i]]++;
            while(count_map[s[i]]>2)
            {
                count_map[s[left]]--;
                left++; 
            }
            ans=max(ans,i-left+1);
        }
        return ans;

    }
};

2.2 求最短/最小 (至少)

例题：209. 长度最小的子数组

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

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

我们枚举右端点，维护左端点

​ 子数组右端点：right

​ 子数组左端点：left

维护ans：ans=min(ans,right-left+1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left=0,n=nums.size(),sum=0,ans=n+1;
        for(int i=0;i<n;i++)
        {
            sum +=nums[i];
            while(sum - nums[left] >= target)
            {
                sum -= nums[left];
                left++;
            }
            if(sum>=target)
            {
                ans=min(ans,i-left+1);
            }
        }
        return ans>n?0:ans;
    }
};

2.3求子数组个数

2.3.1 越长越合法

我们枚举右端点，维护左端点

​ 子数组右端点：right

​ 子数组左端点：0 ~ left-1

此时 ans+=left即可

也就是 0，1，2，3，4， … ，left-1 都是合法的

此时一共有 left 个合法的的子数组

例题 1358. 包含所有三种字符的子字符串数目

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numberOfSubstrings(string s) {
        int less=0,ans=0,left=0;
        int cnt['c'+1]={};
        for(int i=0;i<s.size();i++)
        {
            char x=s[i];
            cnt[x]++;
            if(cnt[x]==1) less++;
            while(less==3)//>=也行
            {
                cnt[s[left]]--;
                if(cnt[s[left]]==0) less--;
                left++;
            }
            ans += left;
        }
        return ans;
        
    }
};

当有需要判断多个变量是否达标，我们可以使用一个less变量加unordered_map

当一个元素进来，map就++，如果符合条 less就++

在元素出窗口时同样也要判断 不符合条件less就–

此时判断less的个数即可判窗口内情况

当然，在例题这种情况可以不使用less 可以改成while(cnt['a']&&cnt['b']&&cnt['c'])

问：题目中为什么使用的是数组而不是unordered_map？

答：数组会比unordered_map快

2.3.2 越短越合法

我们枚举右端点，维护左端点

​ 子数组右端点：right

​ 子数组左端点：left ~ right

此时ans+=right-left+1

例题： 713. 乘积小于 K 的子数组

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int product=1;
        int left=0,ans=0;
        for(int i=0;i<nums.size();i++)
        {
            product*=nums[i];
            while(product>=k&&left<=i)
            {
                product/=nums[left++];
            }
            ans+=i-left+1;
        }
        return ans;
    }
};

2.3.3 恰好型滑动窗口

  • 方法一：三指针写法

    我们枚举右端点，维护两个左端点

    ​ 子数组右端点：right

    ​ 子数组左端点：left1~left2

    此时ans+=left1-left2

  • 方法二：两次滑动窗口写法

    我们可以将刚好行改变为两次越长越合法型 设为函数f 假设刚好的值为k

    return f(k)-f(k-1) 即可

  • 例题 930. 和相同的二元子数组

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

    • 三指针写法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
        int numSubarraysWithSum(vector<int>& nums, int goal) {
            int left1=0,left2=0,ans=0,sum1=0,sum2=0;
            for(int i=0;i<nums.size();i++)
            {
                sum1+=nums[i];
                sum2+=nums[i];
                while(left1<=i&&sum1>=goal)
                {
                    sum1-=nums[left1];
                    left1++;
                }
                while(left2<=i&&sum2>=goal+1)
                {
                    sum2-=nums[left2];
                    left2++;
                }
                ans+=left1-left2;
                
            }
            return ans;
        }
    };
    • 两次滑动窗口写法

    C++ Lambda 表达式是一种匿名函数对象，用于快速定义轻量级的局部函数。以下是其核心要点：

    [捕获列表](参数列表) -> 返回类型 { 函数体 }

    • 捕获列表：指定外部变量的访问方式（值捕获 [=]、引用捕获 [&] 或混合捕获 [x, &y]）。
    • 参数列表：与普通函数参数类似（可省略为空 ()）。
    • 返回类型：可自动推导（省略时根据 return 语句推断），显式声明需用 -> 指明。
    • 函数体：实现逻辑的代码块
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public:
        int numSubarraysWithSum(vector<int>& nums, int goal) {
            auto f=[&](int k)->int{
                int ans=0,left=0,n=nums.size(),sum=0;
                for(int i=0;i<n;i++)
                {
                    sum+=nums[i];
                    while(i>=left&&sum>k)//如果这里用sum>=k（越长越合法型）,后面就需要改成f(goal)-f(goal+1)
                    {
                        sum-=nums[left];
                        left++;
                    }
                    ans+=left;
                }
                return ans;
            };
            return f(goal-1)-f(goal);
        }
    };

写在后面

感谢 灵茶山艾府 大佬的题单和解析，我受益良多

本文用于纪念 2025年5月9日 完成滑动窗口与双指针章节学习

参考资料：

分享｜如何科学刷题？- 讨论 - 力扣（LeetCode）