• 滑动窗口算法

    目录

    1.滑动窗口算法介绍

    1.1 什么是滑动窗口？

    1.2 什么时候用滑动窗口？

    题目：长度最小的子数组

    解法：

    总结：

    1.3 怎么用滑动窗口？

    1.4 滑动窗口的正确性

    1.5 滑动窗口的时间复杂度

    2.相关OJ题

    2.1 长度最小的子数组

    2.1.1 题目

    2.1.2 算法

    2.1.3 代码

    2.2 无重复字符的最长子串

    2.2.1 题目

    2.2.2 算法

    2.2.3 代码

    2.3 最大连续1的个数

    2.3.1 题目

    2.3.2 算法

    2.3.3 代码

    2.4 把x减为0的最小操作数

    2.4.1 题目

    2.4.2 算法

    2.4.3 代码

    2.5 水果成篮

    2.5.1 题目

    2.5.2 算法

    2.5.3 代码

    2.6 找出字符串中所有的字母异位词

    2.6.1 题目

    2.6.2 算法

    2.6.3 代码

    2.7 串联所有单词的子串

    2.7.1 题目

    2.7.2 算法

    2.7.3 代码

    2.8 最小覆盖子串

    2.8.1 题目

    2.8.2 算法

    2.8.3 代码

    3.总结：

    滑动窗口

    1.滑动窗口算法介绍

    1.1 什么是滑动窗口？

    滑动窗口算法是一种常用的双指针算法，主要用于解决字符串和数组相关的问题。它的基本思想是通过维护一个窗口，滑动窗口的起始位置和结束位置以解决问题。

    滑动窗口算法的步骤如下：

    1. 初始化左指针和右指针，分别指向窗口的起始位置。

    2. 当满足问题的条件时，右指针向右移动，扩大窗口范围；当不满足问题的条件时，左指针向右移动，缩小窗口范围。

    3. 在每次移动指针之后，判断当前窗口是否满足问题的条件，如果满足，则根据需要更新结果；如果不满足，则继续移动指针。

    4. 重复步骤2和步骤3，直到右指针到达数组或字符串的末尾。

    滑动窗口算法的优点是在某些情况下，可以将时间复杂度从暴力解法的O(n^2)降低到O(n)。它适用于解决一些查找最长子串、最小覆盖子串、最小窗口子串等问题。

    需要注意的是，在使用滑动窗口算法时，需要定义好窗口的起始位置和结束位置，以及对窗口进行移动和更新的条件。同时，需要考虑边界条件和特殊情况，确保算法的正确性。

    滑动窗口的双指针是同向双指针，两个指针之间的数据可以想象成一个窗口，伴随着这两个指针的移动，这个窗口是在不停向前移动变化的，所以叫滑动窗口。

    1.2 什么时候用滑动窗口？

    题目：长度最小的子数组

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

    找出该数组中满足其总和大于等于target​ 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0​ 。

    示例 1：

    输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3]是该条件下的长度最小的子数组。

    示例 2：

    输入：target = 4, nums = [1,4,4]
输出：1

    示例 3：

    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

    解法：

    解法一：暴力枚举出每一个子数组，从这些子数组中找出长度最小并且和>=target的，返回其长度。O(N^2)

    1. for(int left = 0; left < n; left++)
    2.     for(int right = left; right < n; right++)
    3.     {
    4.         ....
    5.     }

    解法二：滑动窗口

    其实在暴力解法中有很多不必要的枚举，比如：

    • 枚举到一个子数组的sum（子数组的元素总和）>=target时，没有必要向后枚举，因为题目要找最小子数组，后面枚举的子数组sum必定>=target,必然不是后面枚举的子数组。

    • 枚举到一个符合条件的子数组后，left++,right就没有必要退回到left的位置，因为right回退必然导致sum

    总结：

    我们发现，随着right的向后枚举，其sum值是在递增的，也就是sum值是具有单调性的，我们就可以利用这个单调性来进行优化，从而省去很多不必要的枚举，也就是使用滑动窗口算法。

    在整个过程中，right指针的走向：

    1. sum符合条件，即sum >= target，right指针不动。

    2. sum不符合条件，right指针右移。

    整个过程中right指针没有回退，这也是滑动窗口算法的优势所在。

    1.3 怎么用滑动窗口？

    从上面这道题来看：

    1.设置两个同向指针left、right;

    2.进窗口（right指针后移，想象成后面元素进窗口）：sum += nums[right];

    3.

    3.1 判断（视题而定，这里判断的是sum>=target?），根据判断结果决定是否要出窗口（left指针后移），不出则跳过3
​
3.2 更新结果（视题而定，这里更新子数组长度len）,
​
3.3 出窗口
​
3.4 重复3.1~3.3

    4.重复2~3

    注意：

    • 绝大多数的滑动窗口题型的模板都是固定的，但是细节处理上具体题目具体分析。

    • 更新结果的位置不固定，这个要视题目而定。

    1.4 滑动窗口的正确性

    单调性保证了他的正确性。

    1.5 滑动窗口的时间复杂度

    left指针和right指针都最多向后移动n步，复杂度O(N)

    2.相关OJ题

    2.1 长度最小的子数组

    2.1.1 题目

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

    找出该数组中满足其总和大于等于target​ 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0​ 。

    示例 1：

    输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3]是该条件下的长度最小的子数组。

    示例 2：

    输入：target = 4, nums = [1,4,4]
输出：1

    示例 3：

    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

    2.1.2 算法

    1.设置两个同向指针left、right;

    2.进窗口：sum += nums[right];

    3.

    3.1 判断sum>=target?。如果sum >= target，则更新结果并出窗口；如果sum < target，则跳过3。
​
3.2 更新结果（更新子数组长度len）,
​
3.3 出窗口

3.4 重复3.1~3.3

    4.重复2~3

    2.1.3 代码

    1. class Solution {
    2. public:
    3.     int minSubArrayLen(int target, vector<int>& nums) 
    4.     {
    5.         int n = nums.size(), minLen = INT_MAX, sum = 0;
    6.         int left = 0, right = 0;
    7.         for(right = 0; right < n; right++)
    8.         {
    9.             //进窗口
    10.             sum += nums[right];
    11. ​
    12.             //判断
    13.             while(sum >= target)
    14.             {
    15.                 minLen = min(minLen, right - left + 1);//更新结果
    16.                 sum -= nums[left++];//出窗口
    17.             }
    18.         }
    19.         return minLen == INT_MAX ? 0 : minLen;
    20.     }
    21. };

    注意：数组中有不符合条件的子数组，也就是整个数组的sum

    2.2 无重复字符的最长子串

    2.2.1 题目

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

    示例 1:

    输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

    示例 2:

    输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

    示例 3:

    输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

    ​

    2.2.2 算法

    暴力解法：枚举出所有子串，找出符合条件的。

    ‍

    滑动窗口解法：

    题目要求子串不能有重复字符，这里我们可以设置一个哈希表，指针每指向一个元素判断该元素在不在哈希表中，如果该元素不在哈希表中，则放入哈希表；如果已经在哈希表中，则重复字符就能在哈希表中快速查找到。（哈希表的查找效率为O(1)）

    ‍

    1.设置两个同向指针left、right;

    2.进窗口：nums[right]放入哈希表;

    3.

    3.1 判断nums[right]是否在哈希表中。如果在哈希表中，则出窗口；如果不在，则跳过3。
​
3.2 出窗口，a[left]移出哈希表；
​
3.3 重复3.1~3.2

    4.更新结果（子串长度len）

    5.重复2~4

    2.2.3 代码

    1. class Solution {
    2. public:
    3.     int lengthOfLongestSubstring(string s) 
    4.     {
    5.         int hash[128] = {0};
    6.         int left = 0, right = 0, n = s.size();
    7.         int maxLen = 0;
    8.         for(; right < n; right++)
    9.         {
    10.             //进窗口
    11.             hash[s[right]]++;
    12. ​
    13.             //判断
    14.             while(hash[s[right]] > 1)
    15.             {
    16.                 hash[s[left++]]--;//出窗口
    17.             }
    18. ​
    19.             //更新结果
    20.             maxLen = max(maxLen, right - left + 1);
    21.         }
    22.         return maxLen;
    23.     }
    24. };

    2.3 最大连续1的个数

    2.3.1 题目

    给定一个二进制数组 nums​ 和一个整数 k​，如果可以翻转最多 k​ 个 0​ ，则返回 数组中连续 ​​1​​ 的最大个数 。

    示例 1：

    输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

    示例 2：

    输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

    ​

    2.3.2 算法

    这题我们没有必要真的翻转0，可以转化成子数组问题：找出该数组中0的个数不超过k的最长连续子数组。

    那么子数组问题我们又可以使用滑动窗口算法了。

    1.设置两个同向指针left、right;

    2.进窗口：right++并统计0的个数;

    3.

    3.1 判断窗口中0的个数是否大于k。如果大于k，则出窗口；如果不大于k，则跳过3。
​
3.2 出窗口，left++并统计0的个数；
​
3.3 重复3.1~3.2

    4.更新结果（子串长度len）

    5.重复2~4

    2.3.3 代码

    1. class Solution {
    2. public:
    3.     int longestOnes(vector<int>& nums, int k) 
    4.     {
    5.         int n = nums.size(), 
    6.             zeroCount = 0,//统计0的个数
    7.             maxLen = 0;//记录最大长度
    8.         int left = 0, right = 0;
    9.         for(;right < n; right++)
    10.         {
    11.             //进窗口
    12.             if(nums[right] == 0)
    13.                 zeroCount++;
    14. ​
    15.             //判断
    16.             while(zeroCount > k)
    17.             {
    18.                 //出窗口
    19.                 if(nums[left++] == 0)
    20.                     zeroCount--;
    21.             }
    22. ​
    23.             //更新结果
    24.             maxLen = max(maxLen, right - left + 1);
    25.         }
    26.         return maxLen;
    27.     }
    28. };

    2.4 把x减为0的最小操作数

    2.4.1 题目

    给你一个整数数组 nums​ 和一个整数 x​ 。每一次操作时，你应当移除数组 nums​ 最左边或最右边的元素，然后从 x​ 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

    如果可以将 x​恰好 减到 0​ ，返回 最小操作数；否则，返回 -1​ 。

    示例 1：

    输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

    示例 2：

    输入：nums = [5,6,7,8,9], x = 4
输出：-1

    示例 3：

    输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

    ​

    2.4.2 算法

    这种题也需要经过转化变为子数组问题：

    • x减去数组两端元素直到为0，那么这两端移除的元素和为x；

    • 并且每一端元素都是连续的，那么剩余的中间连续元素的和就是sum-x（设为target）（sum是整个数组的和）。

    • 操作数最少，移除元素也就最少，中间剩余元素也就最多。

    可以转化成最长子数组问题：找出该数组中和为sum-x（target）的最长连续子数组。

    ‍

    1.设置两个同向指针left、right;

    2.进窗口：add += nums[right];(add为子数组所有元素之和)

    3.

    3.1 判断add > target?。如果大于target，则出窗口；如果不大于target，则跳过3。
​
3.2 出窗口，add -= nums[left]；
​
3.3 重复3.1~3.2

    4.更新结果（如果add == target,更新子串长度len）

    5.重复2~4

    2.4.3 代码

    1. class Solution {
    2. public:
    3.     int minOperations(vector<int>& nums, int x) 
    4.     {
    5.         int n = nums.size(), 
    6.             add = 0,//子数组所有元素之和
    7.             sum = 0,//所有元素之和
    8.             maxLen = -1;//记录最大长度
    9. ​
    10.         for(auto e : nums)
    11.             sum += e;  
    12. ​
    13.         int target = sum - x;
    14.         //细节问题
    15.         if(target < 0)
    16.             return -1;
    17. ​
    18.         int left = 0, right = 0;
    19. ​
    20.         for(; right < n; right++)
    21.         {
    22.             //进窗口(add < target)
    23.             add += nums[right];
    24. ​
    25.             //判断
    26.             while(add > target)
    27.             {
    28.                 //出窗口(add > target)
    29.                 add -= nums[left++];
    30.             }
    31. ​
    32.             //更新结果(add == target)
    33.             if(add == target)
    34.                 maxLen = max(maxLen, right - left + 1);
    35.         }
    36.         return maxLen == -1 ? -1 : n - maxLen;
    37.     }
    38. };

    2.5 水果成篮

    2.5.1 题目

    你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits​ 表示，其中 fruits[i]​ 是第 i​ 棵树上的水果 种类 。

    你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

    • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。

    • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。

    • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

    给你一个整数数组 fruits​ ，返回你可以收集的水果的 最大 数目。

    示例 1：

    输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

    示例 2：

    输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

    示例 3：

    输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

    示例 4：

    输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

    ​

    2.5.2 算法

    根据题目理解，这题也可以转化成最长子数组的问题：

    1. 不能跳着摘水果，说明是连续子数组。

    2. 两个篮子，每个篮子只能装一种水果，说明你只能装两种水果，也就是连续子数组中只能有两种水果。

    3. 返回可以收集的水果的最大数目，也就是数组中水果种类不超过两种的最长连续子数组问题。

    ‍

    • 还有一个问题就是，水果种类数如何统计？这里用到了哈希表。

    • 单单一个哈希表还不能解决问题，我们需要的是hashmap ，第一个int记录水果的种类，第二个int记录该种类水果的个数；在出窗口的过程中，只有当一种水果的个数为0时，我们才能从哈希表中移除该种类的水果。

    ‍

    算法步骤：

    1.设置两个同向指针left、right;

    2.进窗口：hash[nums[right]]++;

    3.

    3.1 判断窗口中水果种类数（hash.size()）是否超过了两种。如果超过，则出窗口；如果没超过，则跳过3。
​
3.2 出窗口，hash[nums[left]]--,如果减到0，则从哈希表移除该元素；
​
3.3 重复3.1~3.2

    4.更新结果（子数组长度len）

    5.重复2~4

    2.5.3 代码

    1. class Solution {
    2. public:
    3.     int totalFruit(vector<int>& fruits) 
    4.     {
    5.         int n = fruits.size(),
    6.             maxLen = 0;
    7. ​
    8.         unordered_map<int, int> hashmap;//统计子数组水果种类数
    9. ​
    10.         int left = 0, right = 0;
    11. ​
    12.         for(;right < n; right++)
    13.         {
    14.             //进窗口
    15.             hashmap[fruits[right]]++;//插入、查找 + 出现次数修改
    16. ​
    17.             //判断
    18.             while(hashmap.size() > 2)
    19.             {
    20.                 //出窗口
    21.                 hashmap[fruits[left]]--;
    22.                 //次数为0后，从哈希表中移除该水果
    23.                 if(hashmap[fruits[left]] == 0)
    24.                     hashmap.erase(fruits[left]);
    25. ​
    26.                 left++;
    27.             }
    28. ​
    29.             //更新结果
    30.             maxLen = max(maxLen, right - left + 1);
    31.         } 
    32.         return maxLen;
    33.     }
    34. };

    哈希表优化：

    1. //哈希表优化
    2. class Solution {
    3. public:
    4.     int totalFruit(vector<int>& fruits) 
    5.     {
    6.         int n = fruits.size(),
    7.             maxLen = 0;
    8. ​
    9.        int hash[100001] = {0};//统计每种水果的数量
    10.        int kinds = 0;//维护水果种类数
    11. ​
    12.         int left = 0, right = 0;
    13. ​
    14.         for(;right < n; right++)
    15.         {
    16.             //进窗口
    17.             if(hash[fruits[right]] == 0)
    18.                 kinds++;
    19.             hash[fruits[right]]++;//插入、查找 + 出现次数修改
    20. ​
    21.             //判断
    22.             while(kinds > 2)
    23.             {
    24.                 //出窗口
    25.                 hash[fruits[left]]--;
    26.                 //次数为0后，从哈希表中移除该水果
    27.                 if(hash[fruits[left]] == 0)
    28.                     kinds--;
    29. ​
    30.                 left++;
    31.             }
    32. ​
    33.             //更新结果
    34.             maxLen = max(maxLen, right - left + 1);
    35.         } 
    36.         return maxLen;
    37.     }
    38. };

    2.6 找出字符串中所有的字母异位词

    2.6.1 题目

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

    异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

    示例 1:

    输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

    ​ 示例 2:

    输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

    ​

    2.6.2 算法

    首先我们先解决如何判断两个str是字母异位词：

    1. 两个str排序，检查是否相同。 nlogn + n.

    2. 把两个str的字符分别放入两个哈希表中，然后检查两个哈希表是否相同。O(n)

    显然方法二更优。

    ‍

    如何找出s中和p互成异位词的子串，这种子串问题就可以转化成滑动窗口问题：

    1.开辟两个哈希表：hash1、hash2，字符串p的所有元素放入hash1中；

    2.设置两个同向指针left、right;

    3.进窗口：hash2[s[right]]++;

    4.

    4.1 判断窗口长度是否大于串p的长度len。如果超过，则出窗口；如果没超过，则跳过3。
​
4.2 出窗口，hash2[s[left]]--；

    5.更新结果（如果窗口长度 == len && 两个哈希表完全相同，Push（left））

    6.重复3~5

    2.6.3 代码

    1. class Solution {
    2. public:
    3.     bool checkHash(int* a, int* b, int n)
    4.     {
    5.         for(int i = 0; i < 26; i++)
    6.         {
    7.             if(a[i] != b[i])
    8.                 return false;
    9.         }
    10.         return true;
    11.     }
    12. ​
    13.     vector<int> findAnagrams(string s, string p) 
    14.     {
    15.         int hash1[26] = {0}, hash2[26] = {0};
    16.         vector<int> retV;
    17.         int n = s.size(), len = p.size();
    18.         int left = 0, right = 0;
    19. ​
    20.         //p字符串信息进入hash2
    21.         for(int i = 0; i < len; i++)
    22.         {
    23.             hash2[p[i] - 'a']++;
    24.         }
    25. ​
    26.         for(; right <  n; right++)
    27.         {
    28.             //进窗口
    29.             hash1[s[right] - 'a']++;
    30. ​
    31.             //判断、出窗口
    32.             if(right - left + 1 > len)
    33.                 hash1[s[left++] - 'a']--;
    34. ​
    35.             //更新结果
    36.             if(right - left + 1 == len && checkHash(hash1, hash2, len))
    37.                 retV.push_back(left);
    38.         }
    39.         return retV;
    40.     }
    41. };

    方法二：哈希表优化，不用比较两个哈希表，这种比较难想到。

    类比上一题使用一个变量统计水果种类数，这里我们可以使用一个变量来统计窗口中有效字符的个数（所谓有效字符，就是能在串p中找到所对应的字符）。

    • 如果：hash1[s[right]] <= hash2[s[right]]​，s[right]就是有效字符，count（记录有效字符）++。

    • 如果：hash1[s[right]] > hash2[s[right]]​，s[right]就不是有效字符。

    注意有效字符的更新时机：

    s[right]是在进入哈希表后更新，s[left]是在进入哈希表前更新。

    1. //小优化，不用比较两个数组
    2. class Solution {
    3. public:
    4.     vector<int> findAnagrams(string s, string p) 
    5.     {
    6.         int hash1[26] = {0}, hash2[26] = {0};
    7.         vector<int> retV;
    8.         int n = s.size(), 
    9.             len = p.size(), 
    10.             count = 0;//统计窗口中有效字符的个数
    11.         int left = 0, right = 0;
    12. ​
    13.         //p字符串信息进入hash2
    14.         for(int i = 0; i < len; i++)
    15.         {
    16.             hash2[p[i] - 'a']++;
    17.         }
    18. ​
    19.         for(; right <  n; right++)
    20.         {
    21.             //进窗口
    22.             hash1[s[right] - 'a']++;
    23.             if(hash1[s[right] - 'a'] <= hash2[s[right] - 'a'])//有效字符
    24.                 count++;
    25. ​
    26.             //判断、出窗口
    27.             if(right - left + 1 > len)
    28.             {
    29.                 if(hash1[s[left] - 'a'] <= hash2[s[left] - 'a'])//有效字符
    30.                     count--;
    31. ​
    32.                 hash1[s[left++] - 'a']--;
    33.             }  
    34. ​
    35.             //更新结果
    36.             if(right - left + 1 == len && count == len)
    37.                 retV.push_back(left);
    38.         }
    39.         return retV;
    40.     }
    41. };

    2.7 串联所有单词的子串

    2.7.1 题目

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

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

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

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

    示例 1：

    输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]

解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

    示例 2：

    输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

    示例 3：

    输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

    ​

    2.7.2 算法

    这题如果单独拿出来做的话，是相当难的。但是有前面题目的铺垫就相对简单了一些。

    如果我们把words中的每一个字符串都当做一个字符，那这里的联串子串是不是类似上一题的字母异位词？

    ‍

    那我们就可以类比上一题，使用滑动窗口算法+哈希表来解决这里的问题，但是相比上一题有很多细节上的不同：

    • 哈希表的不同：这里的哈希表我们要放字符串，所以使用unordered_map，pair.second存放的是字符串出现次数。

    • left、right指针的移动长度不同：题目中其实有个关键信息：words​ 中所有字符串 长度相同。这也决定了我们能按照上一题的思路来解决本题，left和right指针每次都要走len（words中每个字符串的长度）步。

    • 滑动窗口的执行次数不同：不能忘记下面两种位置的考虑，否则可能出现遗漏。

    2.7.3 代码

    同样两种，一种比较哈希表，一种使用count变量统计有效字符串个数，不用比较哈希表。

    1. class Solution {
    2. public:
    3.     vector<int> findSubstring(string s, vector& words) 
    4.     {
    5.         vector<int> retV;
    6.         int n = s.size(),
    7.             len = words[0].size(),
    8.             windowsLen = len * words.size();
    9.         string substr;
    10. ​
    11.         unordered_mapint> hash1, hash2;
    12.         for(auto e : words)
    13.         {
    14.             hash1[e]++;
    15.         }
    16. ​
    17.         for(int i = 0; i < len; i++)
    18.         {
    19.             int left = i, right = i;
    20.             for(; right < n; right += len)
    21.             {
    22.                 //进窗口
    23.                 substr = s.substr(right, len);
    24.                 hash2[substr]++;
    25. ​
    26.                 //判断
    27.                 if(right - left + len > windowsLen)
    28.                 {
    29.                     //出窗口
    30.                     substr = s.substr(left, len);
    31.                     if(--hash2[substr] == 0)
    32.                         hash2.erase(substr);
    33. ​
    34.                     left += len;
    35.                 }
    36. ​
    37.                 //更新结果
    38.                 if(right - left + len == windowsLen && hash1 == hash2)
    39.                     retV.push_back(left);
    40.             }
    41.             hash2.clear();
    42.         }
    43. ​
    44.         return retV;
    45.     }
    46. };
    1. class Solution {
    2. public:
    3.     vector<int> findSubstring(string s, vector& words) 
    4.     {
    5.         vector<int> retV;
    6.         int n = s.size(),
    7.             len = words[0].size(),
    8.             windowsLen = len * words.size(),
    9.             count = 0;//统计有效字符串个数
    10.         string substr;
    11. ​
    12.         unordered_mapint> hash1, hash2;
    13.         for(auto e : words)
    14.         {
    15.             hash1[e]++;
    16.         }
    17. ​
    18.         for(int i = 0; i < len; i++)
    19.         {
    20.             int left = i, right = i;
    21.             for(; right < n; right += len)
    22.             {
    23.                 //进窗口
    24.                 substr = s.substr(right, len);
    25.                 hash2[substr]++;
    26.                 if(hash1.count(substr) && hash2[substr] <= hash1[substr])
    27.                     count++;
    28. ​
    29.                 //判断
    30.                 if(right - left + len > windowsLen)
    31.                 {
    32.                     //出窗口
    33.                     substr = s.substr(left, len);
    34.                     if(hash1.count(substr) && hash2[substr] <= hash1[substr])
    35.                         count--;
    36.                     hash2[substr]--;
    37. ​
    38.                     left += len;
    39.                 }
    40. ​
    41.                 //更新结果
    42.                 if(right - left + len == windowsLen && count == words.size())
    43.                     retV.push_back(left);
    44.             }
    45.             hash2.clear();
    46.             count = 0;
    47.         }
    48. ​
    49.         return retV;
    50.     }
    51. };

    2.8 最小覆盖子串

    2.8.1 题目

    给你一个字符串 s​ 、一个字符串 t​ 。返回 s​ 中涵盖 t​ 所有字符的最小子串。如果 s​ 中不存在涵盖 t​ 所有字符的子串，则返回空字符串 ""​ 。

    注意：

    • 对于 t​ 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t​ 中该字符数量。

    • 如果 s​ 中存在这样的子串，我们保证它是唯一的答案。

    示例 1：

    输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

    示例 2：

    输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

    示例 3:

    输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

    ​

    2.8.2 算法

    方法一：暴力枚举+哈希表：枚举出s的每一个子串，判断是否符合条件。

    方法二：滑动窗口+哈希表

    1.为什么能使用滑动窗口算法？

    暴力枚举的过程中也有很多不必要的枚举：

    • right指针走到符合条件（子串覆盖t）的时候，right指针没有必要后移。

    • left++后，right指针不能回退，否则不符合条件。

    结合以上量两点，left指针和right指针都是单向前进，我们可以使用滑动窗口算法进行优化。

    ‍

    2.哈希表的优化

    和前面几题相同，这里我们可以对哈希表进行优化，使用一个变量来记录有效字符个数。

    1.开辟两个哈希表：hash1、hash2，字符串t的所有元素放入hash1中；

    2.设置两个同向指针left、right;

    3.进窗口：hash2[s[right]]++并统计有效字符;

    4.

    4.1 判断子串是否覆盖t（即有效字符数 == t.size()），如果覆盖则更新结果并出窗口；如果没有覆盖，则跳过4。
​
4.2 更新结果（窗口内子串起始位置及长度）,
​
4.3 出窗口
​
4.4 重复4.1~4.3

    5.重复3~4

    2.8.3 代码

    1. class Solution {
    2. public:
    3.     string minWindow(string s, string t) 
    4.     {
    5.         int len1 = s.size(), len2 = t.size();
    6.         int hash1[58] = {0}, hash2[58] = {0};
    7.         int count = 0;//有效字符个数
    8.         int begin = 0, minLen = INT_MAX;//返回的字符串的起始位置和长度
    9. ​
    10.         //t字符串信息读入哈希表
    11.         for(auto e : t)
    12.         {
    13.             hash1[e - 'A']++;
    14.         }
    15. ​
    16.         int left = 0, right = 0;
    17.         for(; right < len1; right++)
    18.         {
    19.             //进窗口
    20.             hash2[s[right] - 'A']++;
    21.             if(hash2[s[right] - 'A'] <= hash1[s[right] - 'A'])
    22.                 count++;
    23. ​
    24.             //判断
    25.             while(count == len2)
    26.             {
    27.                 //更新结果
    28.                 if(right - left + 1 < minLen)
    29.                 {
    30.                     begin = left;
    31.                     minLen = right - left + 1;
    32.                 }
    33. ​
    34.                 //出窗口
    35.                 if(hash2[s[left] - 'A'] <= hash1[s[left] - 'A'])
    36.                     count--;
    37.                 hash2[s[left++] - 'A']--;
    38.             }
    39.         }
    40. ​
    41.         return minLen == INT_MAX ? "" : s.substr(begin, minLen);
    42.     }
    43. };

    3.总结：

    • 题目中有涉及连续子数组或者子串问题的，都可以尝试使用滑动窗口来解决，但是有些子数组或者子串问题不易察觉，需要我们经过一定的分析才能转换成子数组、子串问题，比如：2.3、2.4、2.5、2.7。

    • 有些问题我们需要使用哈希表来解决，但这个哈希表不一定是unordered_map/set,有时可以使用一个数组来解决问题。并且对于两个哈希表的比较，我们也可以优化成对有效数据的统计问题。

    • 滑动窗口解题模板中的更新结果位置不固定，但一般找最长子数组、子串问题是在while循环（判断、出窗口的循环）的外面，找最短子数组、子串问题是在while循环（判断、出窗口的循环）的里面。

    • 滑动窗口问题的关键不在于如何使用滑动窗口，而在于为什么能使用滑动窗口，这里的分析一般是根据暴力解法总结来的，子数组/子串问题的暴力解法一般很容易想出来，根据这个暴力解法我们可以分析能否使用滑动窗口算法。

    ‍

    ‍

  • 相关阅读:
    GPT模型结合Python-GEE遥感云大数据分析、管理与可视化技术
    Rokid AR Lite空间计算套装发布，中国空间计算踏上差异化领先之路
    提升自己最快的方式是什么？
    并发bug之源（二）-有序性
    双Orin PCIe RC&EP模式互通
    R语言读取（加载）txt格式数据为dataframe、查询dataframe中存在缺失值的行
    STM32的寄存器操作
    合成数据: 利用开源技术节约资金、时间和减少碳排放
    SpringCloud 微服务（三）-分布式事务问题
    antv x6让拖拽控件工具箱悬浮在画布上，工具箱区域鼠标按下不生成节点
  • 原文地址：https://blog.csdn.net/qq_63981383/article/details/133551819