本文介绍了滑动窗口算法的原理及其作为双指针特殊形式的应用场景。通过 LeetCode 209、3、1004、1658、904、438、30、76 等经典题目，详细讲解了如何识别问题特征、设计左右指针移动策略以及优化时间复杂度。内容涵盖从暴力枚举到滑动窗口的优化思路，提供了完整的 C++ 代码实现，帮助读者掌握处理连续子数组、子串问题的核心技巧。
双指针算法是常见的基础算法之一，滑动窗口则是其一种特殊情况。本文将介绍滑动窗口的原理及适用场景，并通过多道 LeetCode 例题进行实战讲解。
在使用双指针当中，若出现两个指针从开始到结束一直都是朝着同一个方向移动的，并且都不会出现超另一个方向移动的情况，这种就叫做滑动窗口。之所以称为滑动窗口，是因为两个指针一直朝着同一个方向移动就像一个大小可能会变化的窗口一样。
了解了滑动窗口是什么之后，你可能会有疑惑：滑动窗口该怎么用？为什么算法逻辑是正确的？接下来我们通过一道算法题来解决你的疑惑。
通过题目描述可以看出，该算法题要求从给定的数组当中找到和大于给定值 target 的最小子数组。在此要注意的是题目要求的是子数组，这就使得我们选取的数组元素必须是数组当中一段连续的区间，中间不能有中断。
例如以上的示例 1 我们就不能像以下这样选取数组元素：
在没有思路之前，我们先能想到使用暴力枚举来解决。先创建一个指针 left 来遍历原数组，之后再创建一个指针 right 每次从遍历时 left 的下标位置开始向后移动，并且再创建一个变量统计 left 到 right 这段区间内的元素值之和。每次统计之后再判断 sum 是否大于等于 target，是的话就停止这一个 left 位置的子区间统计；并且记入这时子数组的长度，将 left 向后移动一位进行下一次的统计。最后当 left 移动到超出数组的范围之后就结束了所有满足条件的子数组的统计，最后将满足条件的长度最小的子数组长度返回即可。
通过以上算法实现在最坏的情况下要遍历数组两遍，因此暴力枚举的时间复杂度就为 O(N^2)，这种效率在这道题的数据范围下是会超时的。
那么我们就要想该如何依据暴力枚举的算法来优化。
通过以上使用暴力枚举时的流程图就可以看出其实在过程当中有很多的步骤是在做无用功的。
当 right 移动到的位置 l 之后 left 到 right 区间之间的数组元素和正好大于给定的值 target 时，在暴力枚举当中我们是在将 left 向后移动一位时再将 right 也移动到 left 的位置再进行新一轮的统计。但其实在这个过程就没有必要将 right 回退到 left，这是因为在之前 left 到 right 的区间内的数组之和才恰好大于 target 或者等于 target，这时我们将 left 右移一位之后区间内的和一定是小于或者等于或者大于 target 的，那么就说明不需要再将 right 回退到 left 的位置，这时就直接判断此时 left 到 right 之间的所有元素之和即可；这样就避免了很多的重复计算。
那么以上的算法优化就简单来说就是每次移动 right 指针之前都判断当前 left 到 right 区间内的元素之和是否大于或者等于 target，若不是就将 right++，否则就将 left++，并且每次满足条件的区间都统计长度。这时我们就会发现在这个过程当中 left 都是一直朝着一个方向移动，属于同向双指针，这就符合我们说的滑动窗口的条件。
并且通过以上的分析也就证明了滑动窗口算法的合理性。
并且我们还知道了为什么滑动窗口算法时间复杂度更低
- 窗口寻找的是：以当前窗口最左侧元素（记为
left）为基准，符合条件的情况。也就是在这道题中，从left开始，满足区间和sum >= target时的最右侧（记为right）能到哪里。- 我们既然已经找到从
left开始的最优的区间，那么就可以大胆舍去left。但是如果继续像方法一一样，重新开始统计第二个元素（left）往后的和，势必会有大量重复的计算（因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的）。- 此时，
right1的作用就体现出来了，我们只需将left1这个值从sum中剔除。从right1这个元素开始，往后找满足left2元素的区间（此时right1也有可能是满足的，因为left1可能很小。sum剔除掉left1之后，依旧满足大于等于target）。这样我们就能省掉大量重复的计算。- 这样我们不仅能解决问题，而且效率也会大大提升。
滑动窗口算法在使用时就分为以下的几个步骤：
注意：在不同的算法题下更新是在不同的步骤之后的，在本题就是判断满足大于或者等于 target 的条件之后进行更新。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 定义 len 为满足条件的子数组的最小值，一开始定义为 int 范围内的最大值
// sum 为 left 到 right 区间内的元素值之和
int n = nums.size(), len = INT_MAX, sum = 0;
for (int left = 0, right = 0; right < n; right++) {
// 进窗口
sum += nums[right];
// 判断当前区间是否满足条件
while (sum >= target) {
// 更新最小子数组的长度，如果当前满足条件的区间长度比 len 小就更新
len = min(right - left + 1, len);
// 出窗口
sum -= nums[left++];
}
}
// 最后返回 len 时先判断 len 是否为 INT_MAX；
// 是就说明数组所有元素值之和都无法大于或者等于 target，此时就返回 0
return len == INT_MAX ? 0 : len;
}
};
在以上我们了解滑动窗口算法是什么之后，接下来就通过算法题来巩固该算法的使用。每道算法题还是会分为题目解析、算法原理讲解、代码实现三步来带着你吃透每道算法题，相信通过这些算法题的练习你会对滑动窗口算法有更深的理解。
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的字符串当中找出不含重复字符的最长子串。在此要注意的是子串和之前我们看到的子数组一样都必须是原给定数组或者字符串一段连续的区间。
在看到这道算法题时我们一般是先想到使用暴力枚举的方式来解决，那就是创建两个指针变量 left 和 right；使用 left 来遍历数组之后使用 right 来从每个 left 指针位置开始寻找满足条件的子字符，在此过程中每次子字符串满足条件时就更新最长子串长度 len。最后就可以得到满足条件的最长的子串。
以上示例 1 当中使用暴力枚举的过程图就如下所示：
在此在使用暴力枚举在最坏的情况下要遍历原数组两遍，那么时间复杂度就为 O(N^2)，在这道题给定的数据范围可能会超时。
这时我们就要想如何基于暴力枚举下进行算法的优化将暴力枚举内的重复计算给消除。在暴力枚举当中就可以看出当固定 left 之后从后找满足条件的区间，这时在暴力枚举当中是在 right 移动之后出现子串中出现重复字符就将 left++，并且将 right 移动到 left 的位置。但其实这个将 right 回退的过程是完全没必要的，因为将 left 向后移动一位之后当前到原来 right 的区间满足条件的子串不可能比原来的子串还长，所以这时就不要将 right 回退了，毕竟回退了之后还会移动到当前的位置就没必要做这些无用功了。
所以优化之后的算法简单来说就是当 left 到 right 之间的子串满足条件时就先更新子串的长度，之后直到子串出现重复字符就将 left++；此时 right 不要动，之后进行完 left 的移动之后再进行判断不满足就继续移动 left，直到 left 到 right 的区间内的子串满足条件就继续移动 right。
此时该优化之后的算法 left 和 right 为同向双指针，就属于滑动窗口算法，流程图如下所示：
在此就需要使用一个数组来模拟哈希表，这样就能判断当前 left 到 right 的区间内是否无重复字符。
注：在此 s 由英文字母、数字、符号和空格组成，所以我们开一个大小为 128 的数组就完全足够了。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 创建数组 hash 来模拟哈希表，一开始将表内的数据都初始化为 0
int hash[128] = {0};
// 创建变量 len 来统计满足条件的最长字串长度
int n = s.size(), len = 0;
for (int left = 0, right = 0; right < n; right++) {
// 进窗口，将对应的哈希表内的值个数加一
char in = s[right];
hash[in]++;
// 判断当前 hash 表下标 in 位置是否值大于 1
while (hash[in] > 1) {
// 进行出窗口操作，将 hash 表内下标 out 位置的值减一
char out = s[left];
hash[out]--;
// 将 left 右移一位
left++;
}
// 更新最大子串 len 的长度
len = max(len, right - left + 1);
}
return len;
}
};
以上使用滑动窗口算法实现的代码虽然是两次循环的嵌套，但实际上就遍历一次原字符串 s，时间复杂度为 O(N)。
通过以上的题目描述就可以看出该算法题要我们实现的是将给定的数组内的最多 k 个 0 翻转，最终使得数组内得到的子数组元素全部为 1，返回该子数组的长度。
在此如果在解决这道算法题时如果每次翻转数组当中的 0 是真的将数组当中的元素改变，那么这道算法题就会变得十分的繁琐，因为我们在改变相应数组数组当中的 0 元素时我们不能确保此时的子数组是符合要求中长度最长的子数组，所以在进行下一次查找时原数组的内容已经被修改了，这就会使得接下来的操作都是错误的，因此使用这种方式就需要在一开始再创建一个和原数组一样的数组来保存原数组内的数据。但是这种方式不仅空间复杂度高操作过程还复杂，那么这时就要思考了能不能把题目的问题转化一下呢？
其实在该算法题当中不要去想怎么翻转，不要把问题想的很复杂，这道题的结果无非就是一段连续的 1 中间塞了 k 个 0 嘛。因此，我们可以把问题转化成：求数组中一段最长的连续区间，要求这段区间内 0 的个数不超过 k 个。
因此要求最长的一段连续区间就可以使用滑动窗口来解决了。
在该算法题中要求最长的一段连续区间使用滑动窗口来解决就需要一开始定义两个指针 left 和 right 一开始都指向数组的首元素，之后当数组内的 0 元素个数没有超过 k 时就进行进窗口操作也就是继续将 right 右移一位，如果出现了数组内的 0 元素个数超过 k 就进行出窗口操作也就是将 left 右移一位，直到数组内的 0 元素个数不超过 k 就更新最长子数组的长度，最后当 left 移动到数组的末尾时就完成了整个的操作。
算法的流程图如下所示：
在此我们创建一个变量 count 来统计 left 到 right 区间内的元素 0 的个数。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
// 变量 count 统计窗口内值为 0 的元素个数，len 为满足条件最长的子数组长度
int n = nums.size(), count = 0, len = 0;
for (int left = 0, right = 0; right < n; right++) {
// 进窗口，若 right 指向的数组下标位置的元素值为 0，count 就++
if (nums[right] == 0) count++;
// 判断 count 是否大于 k
while (count > k) {
// 出窗口，若 left 指向的数组下标位置的元素值为 0，count 就--
if (nums[left++] == 0) count--;
}
// 更新最长子数组的长度
len = max(right - left + 1, len);
}
return len;
}
};
通过以上的题目描述就可以看出该算法题要我们求的是在给定的数组当中找出从原数组的两边找到能让 x 减去这些元素值恰好为零时这些元素的最小个数，如果无法实现 x 恰好减到 0 就返回 -1。
在此如果我们是完全按照题目给定的步骤来思考，这道算法题就会很复杂了，复杂的点就在于我们不知道在选取边界的元素时选取得顺序是什么，因为最终最小得元素个数情况下可能全部被选取到的元素都在原数组的左边也可能是全部在原数组的右边，当然也可能既有选取左边的也有右边的。这时我们就会发现如果从被选取元素正着考虑就很难解决了，那么这时我们就应该试着从要解决的事物反面考虑了。
在此在这道题当中我们要从原数组两边当中选取出能使得 x 减到 0 的最小元素个数，其实不就是和求数组当中除被选取的元素之外数组内剩下的元素个数最多情况；这时数组当中除被选取的元素为最多且个数就为原数组的长度减去未被选择的元素个数。在此如果无法实现 x 恰好减到 0 这时未被选取到的元素个数就等于数组的长度。
这里我们就创建一个变量 sum 存储数组当中所有元素值减去给定值 x 的结果。
所以综上分析就可以得出该算法题被我们转化为求数组当中和为 sum 的子数组当中最长的子数组长度，如果找不到一个子数组内的元素值为 sum 就返回 -1。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// s 变量统计数组内所有元素值得和，len 为最终窗口和内元素值为 sum 的最小值
int sum = 0, s = 0, len = -1, n = nums.size();
// 遍历原数组统计数组元素之和
for (auto i : nums) s += i;
// sum 变量为 s 变量减去 x 变量的差
sum = s - x;
// 处理特殊情况当 sum 小于 0 时就说明数组内不可能实现元素之和为 x
if (sum < 0) return -1;
// 进行滑动窗口操作，count 统计窗口内的所有元素值之和
for (int count = 0, left = 0, right = 0; right < n; right++) {
// 进窗口，将 right 指向的下标位置的数组元素加到 count 变量内
count += nums[right];
// 判断当前窗口内的和是否大于 sum
while (count > sum) {
// 出窗口，将 left 指向的下标位置的数组元素值从 count 中减去
count -= nums[left++];
}
// 更新 len 变量的值
if (count == sum) len = max(right - left + 1, len);
}
// 返回时判断是否有窗口和为 sum
return len == -1 ? -1 : n - len;
}
};
在以上代码中我们仅仅遍历一次原数组就实现题目要求，代码的时间复杂度为 O(N)。
在这道看完题目你可能会比较疑惑，但其实这道题简单来说就是题目给定了一个数组，数组当中的每个元素就代表一个水果，并且同类型的水果使用同一个数来表示，例如示例 1 当中数组元素为 [1,2,1] 那么数组当中其实就有两种类型的水果分别是 1 和 2。
在此给了我们两个篮子来装水果，要求每个篮子内的水果类型要相同，而且在采摘水果过程中必须要连续采摘不能跳跃之后采摘，就例如在示例 2 当中我们不能采摘完 1 之后跳过 1 去采摘 2。
在这道算法题当中其实要求的就是取在数组当中取出一段子数组，要求子数组当中元素的类型不超过两种，这时返回这段子数组的长度。
那么这时我们使用暴力枚举就是从数组第一个元素开始遍历对应位置之后找出满足条件的子数组，最终返回最长的子数组长度。但根据之前的经验就可以知道这种情况下暴力枚举是有很多重复计算，在此根据单调性其实就可以将原来的暴力枚举优化为滑动窗口，只要窗口内整型类型小于等于 2 就进行进窗口的操作，直到窗口内的类型大于 2 就进行出窗口的操作，最后在出窗口之后更新最长的子数组长度。
在该算法题当中使用滑动窗口算法的流程图如下所示：
在此在这道题当中我们要记录窗口内的元素类型以及对应元素的个数，在此就需要用到哈希表；可以选择使用数组来模拟哈希表也可以直接使用容器 unordered_map。
使用数组来模拟哈希，以下
kind为窗口内的元素种类数，len为满足条件的最长的子数组使用 STL 内的
unordered_map就不需要创建变量kind来统计 hash 表内的元素个数，直接通过调用size()即可实现
用数组模拟哈希表版：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
const int N = 1e5 + 5;
// 使用数组模拟哈希表
int hash[N] = {0};
// len 为满足条件最长的子数组长度
int n = fruits.size(), len = -1;
for (int left = 0, right = 0, kind = 0; right < n; right++) {
// 进窗口，当在哈希表内 in 下标位置在插入之前值为 0 就说明有新的元素插入哈希表就将 kind++
int in = fruits[right];
if (hash[in]++ == 0) kind++;
// 判断当前窗口内的元素种类是否大于 2
while (kind > 2) {
// 出窗口，当在哈希表内 out 下标位置在删除之后值为 0 就说明有一个类型元素从哈希表内删除，这时就将 kind--
int out = fruits[left];
if ((--hash[out]) == 0) kind--;
left++;
}
// 更新 len
len = max(len, right - left + 1);
}
return len;
}
};
使用容器版：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
// 创建 unordered_map 对象来存储相应的元素以及对应的个数
unordered_map<int, int> hash;
int n = fruits.size(), len = -1;
for (int left = 0, right = 0; right < n; right++) {
// 进窗口
int in = fruits[right];
hash[in]++;
while (hash.size() > 2) {
// 出窗口
int out = fruits[left];
hash[out]--;
// 当 hash 对象内 out 元素内的 second 为 0 时
// 就说明现在窗口内已经没有该元素就调用 erase 实现删除操作
if (hash[out] == 0) hash.erase(out);
left++;
}
len = max(len, right - left + 1);
}
return len;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是要在字符串 s 当中找到 p 字符串的所有字母异位词的起始索引，在此也就是要返回所有字串的首元素的地址。那么要了解的是什么是字符串的字母异位词，其实字符串的字母异位词就是只要是由字符串当中的元素组合出的字符串。例如以下示例。
在示例 1 当中字符串 abc 的字母异位词就是使用 a、b、c 三个元素组合出的字符串。满足要求的就为 abc、acb、bac、bca、cab、cba。
在这道题当中如果我们使用暴力枚举来从字符串 s 当中找出字符串 p 的所有字母异位词就需要一开始创建指针变量 left 一开始指向字符串 s 当中的首元素，创建一个哈希表 1 来存储字符串 p 内的元素；再创建一个哈希表 2 来存储 left 之后的三个元素。之后使用 left 遍历字符串 s 直到倒数第三个元素，每次遍历时都将 left 之后的三个元素存放到哈希表当中，比较此时的哈希表 1 和哈希表 2 是否内的元素是否相等，是的话就说明这三个字符是字符串 p 的字母异位词。接下来将 left++ 之后将哈希表内的元素值重新赋值为 0，再重复以上的操作直到 left 移动到字符串 s 的末尾。这时就可以将所有字母异位词的首元素坐标找出。
在以上暴力枚举算法当中我们需要遍历一次字符串 s 并且每次遍历到了 left 之后要将 left 位置开始的三个字符存放到哈希表当中，这样算法的效率是很低的，那么接下来我们就要想着该如何来优化暴力解法。
在此由于暴力解法当中的特性我们就可以试着将暴力解法优化为滑动窗口，在此就需要再创建一个变量 right 来表示窗口的右边界，当哈希表 2 内的元素种类和和个数大于哈希表 1 的时就将进行出窗口操作，直到当哈希表 2 内的元素种类和和个数和哈希表内相等就进行更新对应的索引位置。
使用滑动窗口算法的流程图如下所示：
在以上当中
len表示的是字符串p的长度，len2表示的left到right窗口的长度，count1表示的字符串p当中的元素种类数，count2表示的是left到right窗口内的字符种类数。在以上我们使用这种方法来实现时就需要在更新时在对哈希表 1 和哈希表 2 内的进行遍历比较，只有两个表内的元素完全相同才能说明此时窗口内的字符串示字符串
p的字母异位词，在len1==len2并且count1==count2还要进行判断是因为可能会出现窗口内的总的字符个数相同并且字符类型相同但是各个元素不一定完全相同，就例如 aab 和 abb 这种情况。
在以上我们的算法已经能解决该算法题，但我们在进行更新时还是要对哈希表 hash 进行遍历，虽然在该题中 s 和 p 仅包含小写字母这就使得只需要进行 26 次的比较，效率还不会很低下。但是这时你可能就会好奇是否有更好的解法呢？
其实是有的，在这我们就不再去统计窗口内的元素个数而是需要统计窗口内的有效元素个数，那么有效元素个数是什么呢？
有效元素就是窗口内的元素可对应到字符串 p 内的元素，在此就创建一个变量 sum 来存储有效元素的个数，因此在进行进窗口操作之前就需要判断 hash2[s[right-'a']] 是否小于等于 hash1[s[right-'a']]，是的话就说明这时的元素为有效元素就将 sum++，在出窗口之前判断 hash2[s[left]-'a'] 是否小于等于 hash1[s[left]-'a']，是的话就说明出此时窗口的元素是有效元素就需要将 sum--。
那么在出窗口操作时就只需要判断当前窗口的长度 len 是否大于字符串 p 的长度，是的话就只需要进行一次出窗口操作，出窗口之后如果 len==sum 再进行更新将这时的 left 下标插入到 ret 当中。
例如以下示例：
通过以上的流程图就可以看出在字符串 abcabcbb 当中关于字符串 abca 的字母异位词索引只有 0。
优化前面代码
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> v;
int len1 = p.size(), count1 = 0;
int m[26] = {0}, mp[26] = {0};
for (auto& x : p) {
if (m[x - 'a'] == 0) count1++;
m[x - 'a']++;
}
int left = 0, n = s.size(), len2 = 0, count2 = 0;
for (int right = 0; right < n; right++) {
// 进窗口
if (mp[s[right] - 'a'] == 0) count2++;
mp[s[right] - 'a']++;
len2 = right - left + 1;
while (len2 > len1) {
// 出窗口
mp[s[left] - 'a']--;
if (mp[s[left] - 'a'] == 0) count2--;
left++;
len2 = right - left + 1;
}
// 更新
if (count2 == count1 && len1 == len2) {
int flag = 1;
for (int i = 0; i < 24; i++) {
if (m[i] != mp[i]) flag = -1;
}
if (flag == 1) v.push_back(left);
}
}
return v;
}
};
统计窗口内的有效字符个数，优化之后的代码
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
// 创建存储满足条件的字母异位词的字符串索引
vector<int> ret;
// hash1 存储字符串 p 内的元素，hash2 存储字符串 s 内的元素
int hash1[26] = {0}, hash2[26] = {0};
// len 表示字符串 p 的长度
int len = p.size();
// 将 p 的的元素存储到 hash1 内
for (auto& x : p) {
hash1[x - 'a']++;
}
int n = s.size();
// 进行滑动窗口操作，sum 统计窗口内的有效字符数
for (int left = 0, right = 0, sum = 0; right < n; right++) {
int in = s[right] - 'a';
// 进窗口
hash2[in]++;
// 在进窗口之后判断当前字符是否为有效字符，是就 sum++
if (hash2[in] <= hash1[in]) sum++;
// 当窗口的长度大于 len 时就进行出窗口操作
if (right - left + 1 > len) {
// 在出窗口之前判断当前出去的字符是否为有效字符，是的话就将 sum--
int out = s[left] - 'a';
if (hash2[out] <= hash1[out]) sum--;
// 出窗口
hash2[out]--;
left++;
}
// 判断当前的子串是否为 p 的字母异位词，是的话就更新起始位置的索引到 ret 当中
if (sum == len) {
ret.push_back(left);
}
}
return ret;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的字符串当中找出长度为 words 字符串数组当中的所有字符串组成的子串，那么在此也就是要在字符串 s 当中找到字符数组 words 所有的字符串组成的子串。
在这道算法题其实和以上我们解决的找到字符串当中所有的字母异位词那道算法题十分的相识，在此不同点就是在之前的算法题当中我们要找的是满足条件的字母的字母异位词的字符串，而在这道算法题当中需要找到满足条件的由单词组成的子串，在之前的每个元素是一个字符，而在这道题当中每个元素是一个字符串。
那么有了解决之前那道算法题的经验就就可以在这道算法题当中也使用滑动窗口来解决，只不过在此每次进窗口和出窗口时进和出的元素就不单是一个字符而是长度和 words[i].length 一样的字符串。那么在使用滑动窗口的具体过程就是一开始创建两个指向字符串首元素的指针 left 和 right，再创建两个哈希表 hash1 和 hash2 分别存储字符数组 words 和窗口内的字符串，之后创建一个变量 count 来表示窗口内的元素个数，在此在字符串进窗口之后判断 hash2[in] 是否小于等于 hash1[in]，是的话就将有效元素加一；在字符串出窗口之前判断 hash2[in] 是否小于等于 hash1[in]，是的话就将有效元素减一。最后在出窗口之后判断 count 是否等于 words.length()，是的话就将 left 存储到最后返回的 vector 对象当中。
该算法的流程图如下所示：
在此 count1 表示的是数组 words 当中的元素个数，count2 表示的是窗口内的有效元素个数，gap 表示的是数组 words 当中每个元素所对应的字符串的的长度。
在以上看起来已经将该算法题的所有步骤都已经考虑到了，但其实我们有一个点没有考虑。那就是在以上我们只考虑从 s 当中的第一个字符开始，但是其实还要考虑起始为 gap 之前字符的全款。
例如以下示例：
这时如果只考虑从第一个字符开始的情况就最后就只能得到下标 0,2,4,6,8,10。那么在此就还要考虑下标从 1 开始的情况。
所以以上我们实现的算法流程图也就要做出相应的修改，那就是要将滑动窗口的操作进行 gap 次，每次滑动窗口的操作 left 和 right 的初始值也要作出相应的改变。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
// 创建哈希表 hash1 存储字符串数组 words 当中的数据
unordered_map<string, int> hash1;
// 遍历字符串数组 words 当中的数据存储到 hash2 当中
for (auto& x : words) hash1[x]++;
// 变量 gap 表示字符数组当中每个字符串的长度
int gap = words[0].size();
// 变量 len 表示字符串 s 的长度，变量 count1 表示字符串数组 words 的大小
int len = s.size(), count1 = words.size();
// 执行 gap 次
for (int i = 0; i < gap; i++) {
// 创建，哈希表 hash2 存储滑动窗口内的字符串数据
unordered_map<string, int> hash2;
// count2 表示窗口内的有效元素个数
int count2 = 0;
for (int left = i, right = i; right < len; right += gap) {
// 进窗口，将 right 指向的字串进窗口
string tmp = s.substr(right, gap);
++hash2[tmp];
// 在进窗口之后判断进入窗口的字符串是否为有效元素，是的话就 count2++
if (hash1.count(tmp) && hash2[tmp] <= hash1[tmp]) count2++;
// 判断当前窗口的长度是否大于字符串数组总的字符数，是的话就进行出窗口的操作
while ((right - left + gap) / gap > count1) {
string tmp = s.substr(left, gap);
// 在出窗口之前判断当前出窗口的字符串是否为有效元素，是的话就将 count2--
if (hash1.count(tmp) && hash2[tmp] <= hash1[tmp]) count2--;
// 出窗口，将 left 指向的字串出窗口
--hash2[tmp];
left += gap;
}
// 判断 count1 是否等于 count2，是的话就将当前下标 left 插入到 ret 当中
if (count1 == count2) {
ret.push_back(left);
}
}
}
// 返回 vector 对象 ret
return ret;
}
};
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的字符串中找出覆盖字符串 t 所有字符的最小字串，如果无法从 s 当中找出满足条件的字串就返回空串。
例如在以上的示例当中 s 当中所有覆盖字符串 t 的所有字符的字串如下所示：
通过以上的分析就可以得出在字符串 s 当中覆盖字符串 t 的最短字符串是 BANC。
在此在该算法题当中我们可以看到也是在给定的字符串当中寻找满足条件的最小子串，那么根据之前的经验这道算法题也可以使用滑动窗口算法来解决。
这时你可能就会直接想到和之前解决类似的算法题一样创建两个哈希表 hash1 和 hash2 分别存储字符串 t 的字符和窗口内的的字符，创建两个变量 count1 和 count2 分别表示 t 内的字符个数和窗口内的有效字符个数。在进窗口之后判断此时插入到 hash2 当中的字符是否为有效字符；是的话就将之后当窗口内的有效 count2++，在出窗口之前判断此时出的字符是否为有效字符，是的话就将 count2--。最后当 count1==count2 时就进行更新的操作。
以上的算法逻辑确实是可以解决该算法题的，不过在此其实我们还有更好的解决方式就是在窗口内我们统计的不是窗口内有效字符的个数而是去统计窗口内的有效字符种类数，算法的具体改进就是在进窗口之后只有当 hash1[in]==hash2[in] 时才将 count2++，在出窗口之前只有当 hash1[out]==hash2[out] 时才将 count2--，最后当 count1==count2 时就进行更新。
统计窗口内有效元素个数版本算法：
class Solution {
public:
string minWindow(string s, string t) {
int hash1[128] = {0}, hash2[128] = {0};
for (auto x : t) {
hash1[x]++;
}
int n = s.size(), count = t.size();
// 有效元素个数 sum
int left = 0, begin = 0, sum = 0, len = INT_MAX;
// 遍历字符串 s
for (int right = 0; right < n; right++) {
// 进窗口
int in = s[right];
hash2[in]++;
// 进窗口之前判断当前字符是否为有效字符
if (hash2[in] <= hash1[in]) sum++;
while (sum == count) {
// 当字符串 tmp 包含字符串 t 内的所有字符就更新
if (right - left + 1 < len) {
begin = left;
len = right - left + 1;
}
int out = s[left];
// 出窗口之前判断当前字符是否为有效字符
if (hash2[out] <= hash1[out]) {
sum--;
}
hash2[out]--;
left++;
}
}
if (len == INT_MAX) return "";
return s.substr(begin, len);
}
};
统计窗口内的有效字符种类数版算法：
class Solution {
public:
string minWindow(string s, string t) {
// 创建哈希表 hash1 存储字符串 t 当中的字符，哈希表 hash2 存储窗口内的字符
int hash1[128] = {0}, hash2[128] = {0};
// count 变量表示字符串 t 当中的字符种类数
int count1 = 0;
for (auto& x : t) {
// 当此时 x 数组下标对应的 hash1 内的元素值为 0 就说明插入了新类型的元素就将 count1++
if (hash1[x] == 0) count1++;
hash1[x]++;
}
// minlen 统计 s 当中满足条件的最短子串的长度，begin 为该子串的起始位置的索引
int minlen = INT_MAX, begin = -1;
// count2 存储窗口内的有效字符种类数
int n = s.size(), count2 = 0;
for (int right = 0, left = 0; right < n; right++) {
// 进窗口，将此时 hash2 的 in 字符下标对应的元素加一
char in = s[right];
hash2[in]++;
// 进窗口之后判断当前的进入的字符是否为有效种类的字符，是的话就将 count2++
if (hash2[in] == hash1[in]) count2++;
// 判断窗口内的有效个数 count2 是否和 count1 相等，是的话就进行出窗口操作
while (count1 == count2) {
// 出窗口之前更新 minlen 和 begin
if (right - left + 1 < minlen) {
begin = left;
minlen = right - left + 1;
}
char out = s[left++];
// 出窗口之前判断当前出窗口的字符是否为有效种类字符，是的话就将 count2--
if (hash1[out] == hash2[out]) count2--;
// 出窗口
hash2[out]--;
}
}
// 返回子串之前判断进行滑动窗口过程中是否出现符合条件的字串，如果没有就返回空串
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};
以上就是本篇的全部内容了。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online