多指针）

Tip

题单已老, 请点击链接, 查看最新版!

By 灵茶山艾府

右边数字为难度分。

定长滑动窗口

不定长滑动窗口（求最长/最大）

不定长滑动窗口（求最短/最小）

209. 长度最小的子数组
1234. 替换子串得到平衡字符串 1878 (难)
1574. 删除最短的子数组使剩余数组有序 1932 (难) (不太会这种: 移除子数组)
76. 最小覆盖子串
面试题 17.18. 最短超串

不定长滑动窗口（求子数组个数）

2799. 统计完全子数组的数目 1398 (子数组数量怎么算qwq?!)
713. 乘积小于 K 的子数组
1358. 包含所有三种字符的子字符串数目 1646 (子数组数量怎么算qwq?! 这里你就理解了)
2962. 统计最大元素出现至少 K 次的子数组 1701 (同上的子数组计算方法)
2302. 统计得分小于 K 的子数组数目 1808 (同上的子数组计算方法, 但有不同)
2537. 统计好子数组的数目 1892 (同上的子数组计算方法, 但是使用哈希统计arr[i] == arr[j] (i < j)的对数)
2762. 不间断子数组 1940 (有序列表)
2972. 统计移除递增子数组的数目 II 2153 (不太会这种: 移除子数组)
2743. 计算没有重复字符的子字符串数量（会员题）

多指针滑动窗口

计算可排除前后也可作为子数组的, 问子数组数目, 模版:

0, 1 数组, 问和为goal的子数组数目. 因为可能存在前后缀 [0,0,0,1,0,0], 0 可以使得窗口移动, 因此我们使用两个指针l1, l2作为前面, (l1)一个负责goal窗口, (l2)一个负责goal - 1窗口, 那么就可以得到排除的0的部分, 最后res += l2 - l1即可.

class Solution { // 930. 和相同的二元子数组 code
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size(), res = 0;
        for (int i = 0, l1 = 0, l2 = 0, sum1 = 0, sum2 = 0; i < n; ++i) {
            sum1 += nums[i];
            while (l1 <= i && sum1 > goal)
                sum1 -= nums[l1++];

            sum2 += nums[i];
            while (l2 <= i && sum2 >= goal)
                sum2 -= nums[l2++];

            res += l2 - l1;
        }
        return res;
    }
};
C++