滑动窗口

1888. 使二进制字符串字符交替的最少反转次数

给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：

类型 1 ：删除 字符串 s 的第一个字符并将它添加到字符串结尾。
类型 2 ：选择 字符串 s 中任意一个字符并将该字符反转，也就是如果值为 '0' ，则反转得到 '1' ，反之亦然。

请你返回使 s 变成交替字符串的前提下， 类型 2 的最少操作次数。

我们称一个字符串是交替的，需要满足任意相邻字符都不同。

比方说，字符串 "010" 和 "1010" 都是交替的，但是字符串 "0100" 不是

核心难点 → 计算反转次数
方法一：暴力枚举

对于每个窗口，枚举所需的次数，时间复杂度为O(2 ⋅ n²)

方法二：找规律

注意到，如果要满足题目条件，窗口内必须满足0101⋯或者1010⋯形式

满足$0101则 t[i]= i mod 2$

满足$1010则t[i]i mod 2$

我们将t[i] ≠ i mod 2 的数量设为cnt

当窗口左端点的下标为偶数时，cnt为满足1010⋯的操作类型2的总次数，n - cnt则为满足0101⋯的操作类型2的总次数，当窗口左端点的下标为奇数时则相反

对于每个窗口，都可以改为1010⋯或者0101⋯形式，所以，每个窗口的操作次数应为

min (cnt, n − cnt)

for (int i = 0; i < 2 * n - 1; i++){
    if (s[i % n] % 2 != i % 2) cnt++;
    int left = i - n + 1;
    if (left < 0) continue;
    ans = min({ans, cnt, n - cnt});
    if (s[left] % 2 != i % 2) cnt--;
}

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的子串。

解决方法：

对于s1，用cnt[]来记录每个字母出现的次数，用less来记录s1中字母有多少种

对于每个窗口，cnt[s2[i]]如果归零，则less--，如果该窗口能使less == 0，则符合条件

int cnt[26], less; // cnt[],less初始化如上文
int n = s2.size(), m = s1.size();
if (m > n) return false;
for (int i = 0; i < n; i++){
    int in = s[i] - 'a';
    cnt[in]--;
    if (cnt[in] == 0) less--;
    int left = i - m + 1;
    if (less == 0) return true;
    int out = s[left] - 'a';
    if (cnt[out] == 0) less++;
    cnt[out]++;
}
return false;

30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

My Solution O(n ⋅ m)

核心思想，哈希表储存每个word的出现次数，用less储存不同的word的总数，定长滑动窗口来获得答案

n 代表s.length，m表示words内每个word的长度，_m表示words的长度

for (int j = 0; j < m; j++){	//遍历整个s字符串
    int i = i - m + 1 + j;
    for (; i < n; i += m){		//步进每个单词
        string segment = s.substr(i - m + 1, m);
        cnt[segment]--;
        if (cnt[segment] == 0) less--;
        int left = i - m * _m + 1;
        if (left < 0) continue;
        if (less == 0) ans.push_back(left);
        segment = s.substr(left, m);
        if (cnt[segment] == 0) less++;
        cnt[segment]++;
    }
    //考虑到滑动窗口结束时，仍未完全回溯
    for (int left = i - m * _m + 1; left <= n - m; left += m){
        //left <= n - m 从尾部取m个字符时避免越界
        string segment = s.substr(left, m);
        if (cnt[segment] == 0) less++;
        cnt[segment]++;
    }
}

1016. 子串能表示从 1 到 N 数字的二进制串

给定一个二进制字符串 s 和一个正整数 n，如果对于 [1, n] 范围内的每个整数，其二进制表示都是 s 的 子字符串 ，就返回 true，否则返回 false 。

子字符串 是字符串中连续的字符序列。

O(m)算法：

设 n 的二进制数(bit_width)为 k + 1：

单看闭区间 [4, 7] ，有 4 个互不相同的整数，它们的二进制数均为 3，如果要让字符串 s 包含这 4 个数，s 中至少要有 4 个长为 3 的互不相同子串，则应满足 m ≥ 3 + (4 − 1) = 6 ，否则返回false

区间 [2^k, n] 内每个数的二进制数为 k + 1 ，一共有 n − 2^k + 1个，所以应满足m ≥ k + 1 + (n − 2^k + 1 − 1) = k + 1 + n − 2^k
区间 [2^k − 1, 2^k − 1] 内每个数的二进制数为 k ，一共有 2^k − 1 个，所以应满足 m ≥ k + 2^k − 1 − 1
注意，当 n = 1 时，k = 0 ，此时需要特判，检查 s 中是否包含 1

注意到 [2^k − 1, 2^k] 区间内的所有数字都右移 1 位，便能得到 [2^k − 2, 2^k − 1 − 1] 内的所有数字，如果 s 包含 [2^k − 1, 2^k] 内的所有二进制数，则必能得到 [2^k − 2, 2^k − 1 − 1] 内的所有二进制数，所以仅需考虑 $[2^{k-1},2k] $ 即可，综上，只需考虑 s 内是否包含 [2^k − 1, 2^k − 1] 和 [2^k, n] 的所有二进制数即可

因此，如果 m < max(k + 1 + n − 2^k, k + 2^k − 1) 可以直接返回false

进一步的， [2^k, n] 能够得到 [2^k − 1, ⌊n/2⌋] ，所以对于 [2^k − 1, 2^k − 1] 来说，只需从 ⌊n/2⌋ + 1 来考虑即可

bool queryString(string s, int n) {
        int k = bit_width((unsigned int)n) - 1;
        int m = s.length();
        if (n == 1) return s.find('1') != string::npos;
        if (m < max(1 + k + n - (1 << k), k + (1 << (k - 1)) - 1)) return false;
        auto check = [&](int k, int lower, int upper) -> bool {
            if (lower > upper) return true;
            unordered_set<int> seen;
            int mask = (1 << (k - 1)) - 1;
            int x = stoi(s.substr(0, k - 1), nullptr, 2);//将二进制转换为十进制
            for (int i = k - 1; i < m; i++){
                x = ((x & mask) << 1) | (s[i] - '0');//实现出->入窗口
                if (lower <= x && x <= upper)
                    seen.insert(x);
            }
            return seen.size() == upper - lower + 1;
        };
        return check(k, n / 2 + 1, (1 << k) - 1) && check(k + 1, 1 << k, n);
    }

2831. 找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

核心→分组

我们可以枚举每位数字在数组的下标，比较两个下标间应该删除元素的数量与 k 的大小来决定是否移窗口

使用 vector<vector<int>> pos_lists 来记录

最关键步骤：pos_lists[x].push_back(i - pos_lists[x].size());

假设数组为：[1, 2, 1, 3, 1, 4, 1]，我们关注数值 1

数值1的位置：索引 0, 2, 4, 6

传统思路：

保留位置0和2：需要删除索引1处的元素(2) → 删除1个
保留位置0,2,4：需要删除索引1(2)和索引3(3) → 删除2个
保留位置0,2,4,6：需要删除索引1(2)、索引3(3)、索引5(4) → 删除3个

转换思路： 对于第 j 个1（从0开始计数），计算：原始位置 - j

第0个1（位置0）：0 - 0 = 0
第1个1（位置2）：2 - 1 = 1
第2个1（位置4）：4 - 2 = 2
第3个1（位置6）：6 - 3 = 3

得到转换后位置：[0, 1, 2, 3]，可以发现，得到了前 j 个 1 要删除的数

对于 left 处和 right 处的数字 x，所需要删除的数量变为 pos[right] − pos[left]

如果 pos[right] − pos[left] > k 则缩小窗口，最长的答案应为 max(ans, right − left + 1)

2537. 统计好子数组的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中好子数组的数目。

一个子数组 arr 如果有至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个好子数组。

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

核心思想，统计窗口内每个 x 出现的个数，记为 cnt[x]

考虑维护窗口，当进入的数为 x 时，窗口内便会有 cnt[x] 个数与之相匹配，同理，当 nums[left] 离开窗口时，窗口内便有 cnt[x] − 1 个数失去匹配

long long ans = 0;
        int left = 0, sum = 0;
        unordered_map<int, int> cnt;
        for (auto &x : nums){
            cnt[x]++;
            sum += cnt[x] - 1;
            while (sum >= k){
                sum -= cnt[nums[left++]] - 1;
            }
            ans += left;
        }
        return ans;

#滑动窗口 #C++ #基础算法 #leetcode

滑动窗口

http://example.com/2025/11/12/1/

作者

Suzuran

发布于

2025年11月12日

许可协议

滑动窗口题型总结上一篇

Test 下一篇

滑动窗口

1888. 使二进制字符串字符交替的最少反转次数

核心难点 → 计算反转次数

567. 字符串的排列

30. 串联所有单词的子串

My Solution O(n ⋅ m)

1016. 子串能表示从 1 到 N 数字的二进制串

2831. 找出最长等值子数组

2537. 统计好子数组的数目