当前位置:   article > 正文

探索算法系列 - 滑动窗口

探索算法系列 - 滑动窗口

目录

长度最小的子数组(原题链接)

无重复字符的最长子串(原题链接)

最大连续1的个数 III(原题链接)

将 x 减到 0 的最小操作数(原题链接)

水果成篮(原题链接)

找到字符串中所有字母异位词(原题链接)

串联所有单词的子串(原题链接)

最小覆盖子串(原题链接)


长度最小的子数组(原题链接)

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

找出该数组中满足其总和大于等于 target 的长度最小的 子数组

并返回其长度如果不存在符合条件的子数组,返回 0 。

 解题思路

  1. 滑动窗口:使用滑动窗口的方法,通过两个指针 leftright 来表示窗口的左右边界,用于寻找满足条件的子数组。
  2. 动态调整窗口大小:通过移动 right 指针扩展窗口,直到窗口内的元素和大于或等于目标值 target,然后移动 left 指针收缩窗口,以便找到满足条件的最短子数组。
  3. 最小长度:在每次窗口满足条件时,更新最小子数组长度。

步骤说明

  1. 初始化

    • 变量 n 用来保存数组 nums 的长度。
    • 变量 sum 用来保存当前窗口内的元素和。
    • 变量 len 用来保存满足条件的最短子数组的长度,初始值为 INT_MAX 表示无穷大。
    • 两个指针 leftright 都初始化为 0,表示窗口的左右边界。
  2. 遍历数组

    • 使用 for 循环遍历数组,right 指针从 0 到 n-1
    • 每次将当前元素 nums[right] 加到 sum 中,扩展窗口的右边界。
  3. 收缩窗口

    • 使用 while 循环检查当前窗口内的元素和 sum 是否大于或等于目标值 target
    • 如果满足条件,更新最短子数组长度 len 为当前窗口长度 right - left + 1 和之前的最小长度之间的较小值。
    • 将窗口左边界元素 nums[left]sum 中减去,并将 left 指针右移,收缩窗口的左边界。
  4. 返回结果

    • 如果 len 仍然是 INT_MAX,表示没有找到满足条件的子数组,返回 0。
    • 否则,返回 len

 具体代码

  1. class Solution
  2. {
  3. public:
  4. int minSubArrayLen(int target, vector<int>& nums)
  5. {
  6. int n = nums.size(); // 数组长度
  7. int sum = 0; // 当前窗口内元素的总和
  8. int len = INT_MAX; // 记录最短子数组的长度,初始值为最大整数
  9. for (int left = 0, right = 0; right < n; right++)
  10. {
  11. sum += nums[right]; // 进窗口,更新总和
  12. while (sum >= target) // 如果窗口内总和满足条件,尝试收缩窗口
  13. {
  14. len = min(len, right - left + 1); // 更新最短子数组的长度
  15. sum -= nums[left]; // 移动左边界,减少总和
  16. left++;
  17. }
  18. }
  19. return len == INT_MAX ? 0 : len; // 如果未找到满足条件的子数组,返回 0,否则返回最短子数组长度
  20. }
  21. };

无重复字符的最长子串(原题链接)

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

解题思路

  1. 滑动窗口:使用滑动窗口的方法,通过两个指针 leftright 来表示窗口的左右边界,用于寻找最长的无重复字符子串。
  2. 哈希数组:使用哈希数组 hash 记录每个字符在当前窗口内出现的次数。
  3. 动态调整窗口大小:通过移动 right 指针扩展窗口,直到窗口内有重复字符,然后移动 left 指针收缩窗口,以便保持窗口内的字符都是唯一的。
  4. 最大长度:在每次窗口内没有重复字符时,更新最长子串的长度。

步骤说明

  1. 初始化

    • 变量 hash 用来记录每个字符在当前窗口内出现的次数,大小为128(因为ASCII字符一共128个)。
    • 变量 leftright 初始化为 0,表示窗口的左右边界。
    • 变量 n 用来保存字符串 s 的长度。
    • 变量 ret 用来保存最长无重复字符子串的长度,初始值为 0。
  2. 遍历字符串

    • 使用 while 循环遍历字符串,当 right 小于 n 时进行循环。
    • 每次将当前字符 s[right]hash 中的值加1,扩展窗口的右边界。
  3. 收缩窗口

    • 使用 while 循环检查当前窗口内的字符 s[right] 是否出现多次。
    • 如果出现多次,则将窗口左边界字符 s[left]hash 中的值减1,并将 left 指针右移,收缩窗口的左边界,直到窗口内字符都是唯一的。
  4. 更新最大长度

    • 在每次窗口内字符都是唯一时,更新最长子串的长度 ret 为当前窗口长度 right - left + 1 和之前的最大长度之间的较大值。
  5. 返回结果

    • 返回 ret,即最长无重复字符子串的长度。

 具体代码

  1. class Solution
  2. {
  3. public:
  4. int lengthOfLongestSubstring(string s)
  5. {
  6. int hash[128] = { 0 }; // 记录字符的频次
  7. int left = 0, right = 0, n = s.size(); // 初始化左右边界和字符串长度
  8. int ret = 0; // 记录最长子字符串的长度
  9. while (right < n)
  10. {
  11. hash[s[right]]++; // 进窗口,更新当前字符的频次
  12. while (hash[s[right]] > 1) // 如果窗口内有重复字符,收缩窗口
  13. hash[s[left++]]--; // 移动左边界,并更新频次
  14. ret = max(ret, right - left + 1); // 更新结果
  15. right++; // 移动右边界
  16. }
  17. return ret; // 返回最长不包含重复字符的子字符串长度
  18. }
  19. };

最大连续1的个数 III(原题链接)

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

 解题思路

  1. 滑动窗口:使用滑动窗口的方法,通过两个指针 leftright 来表示窗口的左右边界,用于寻找包含最多 k 个 0 的最长连续子数组。
  2. 计数器:使用变量 zero 记录当前窗口内 0 的数量。
  3. 动态调整窗口大小:通过移动 right 指针扩展窗口,直到窗口内的 0 的数量超过 k,然后移动 left 指针收缩窗口,以便保持窗口内的 0 的数量不超过 k
  4. 最大长度:在每次窗口内的 0 的数量不超过 k 时,更新最长子数组的长度。

 步骤说明

  1. 初始化

    • 变量 ret 用来保存包含最多 k 个 0 的最长连续子数组的长度,初始值为 0。
    • 变量 leftright 初始化为 0,表示窗口的左右边界。
    • 变量 zero 用来记录当前窗口内 0 的数量,初始值为 0。
  2. 遍历数组

    • 使用 for 循环遍历数组,right 指针从 0 到 nums.size()-1
    • 每次将当前元素 nums[right] 加到窗口中,如果是 0,则 zero 加1。
  3. 收缩窗口

    • 使用 while 循环检查当前窗口内的 0 的数量 zero 是否超过 k
    • 如果超过 k,则将窗口左边界元素 nums[left] 从窗口中移出,并将 left 指针右移,如果移出的元素是 0,则 zero 减1。
  4. 更新最大长度

    • 在每次窗口内的 0 的数量不超过 k 时,更新最长子数组的长度 ret 为当前窗口长度 right - left + 1 和之前的最大长度之间的较大值。
  5. 返回结果

    • 返回 ret,即包含最多 k 个 0 的最长连续子数组的长度。

 具体代码

  1. class Solution
  2. {
  3. public:
  4. int longestOnes(vector<int>& nums, int k)
  5. {
  6. int ret = 0; // 记录最长子数组的长度
  7. for(int left = 0, right = 0, zero = 0; right < nums.size(); right++)
  8. {
  9. if(nums[right] == 0) // 进窗口
  10. zero++;
  11. while(zero > k) // 如果窗口中的0数量超过k,收缩窗口
  12. {
  13. if(nums[left++] == 0) // 移动左边界
  14. {
  15. zero--;
  16. }
  17. }
  18. ret = max(ret, right - left + 1); // 更新结果
  19. }
  20. return ret; // 返回结果
  21. }
  22. };

将 x 减到 0 的最小操作数(原题链接)

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

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

解题思路

  • 定义变量 sum 计算数组中所有元素的总和,然后定义目标值 targetsum - x
  • 使用滑动窗口的方法找到最长的子数组,其和为 target
  • 最终结果是 nums.size() - ret,即数组的长度减去最长子数组的长度。

步骤说明

  1. 初始化

    • 计算数组 nums 所有元素的总和 sum
    • 计算目标值 targetsum - x
    • 如果 target < 0,返回 -1,因为不可能找到和为负数的子数组。
  2. 定义变量

    • ret 初始化为 -1,用于存储找到的最长子数组的长度。
    • leftright 分别为滑动窗口的左右边界,初始化为 0。
    • tmp 为当前滑动窗口内的元素和,初始化为 0。
  3. 滑动窗口

    • 遍历数组 numsright 从 0 到 nums.size()
    • nums[right] 加到 tmp 中,表示右边界扩展。
    • 如果 tmp 大于 target,不断将 nums[left] 减去 tmp 中,并将 left 右移,表示左边界收缩。
    • 如果 tmp 等于 target,更新 ret 为当前窗口长度,即 right - left + 1
  4. 结果返回

    • 如果 ret 仍然是 -1,返回 -1,表示没有找到满足条件的子数组。
    • 否则返回 nums.size() - ret,即操作次数。

具体代码

  1. class Solution
  2. {
  3. public:
  4. int minOperations(vector<int>& nums, int x)
  5. {
  6. int sum = 0;
  7. for(int a : nums) sum += a; // 计算数组的总和
  8. int target = sum - x; // 计算需要找到的子数组和
  9. if(target < 0) return -1; // 如果目标和小于0,返回-1
  10. int ret = -1; // 记录最长子数组长度
  11. for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
  12. {
  13. tmp += nums[right]; // 进窗口,更新当前和
  14. while(tmp > target) // 如果当前和超过目标,收缩窗口
  15. tmp -= nums[left++];
  16. if(tmp == target) // 如果当前和等于目标,更新最长子数组长度
  17. ret = max(ret, right - left + 1);
  18. }
  19. if(ret == -1) // 如果没有找到符合条件的子数组,返回-1
  20. return ret;
  21. else
  22. return nums.size() - ret; // 返回移除的元素数量
  23. }
  24. };

水果成篮(原题链接)

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

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

  • 你只有 两个 篮子,并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘,你必须从 每棵 树(包括开始采摘的树)上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
  • 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。

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

解题思路

目的是在一个数组 f 中找到包含两种不同元素的最长子数组。该问题可以被视为一个“滑动窗口”问题,通过使用滑动窗口的方法保持一个窗口,使得窗口内最多包含两种不同的元素。

 步骤说明

  1. 初始化

    • 定义一个哈希数组 hash,用于记录每个元素出现的次数,大小为 100001,初始值都为 0。
    • 定义变量 ret,用于记录最长子数组的长度,初始值为 0。
    • 定义滑动窗口的左右边界 leftright,初始值为 0。
    • 定义变量 kinds,用于记录窗口内不同元素的种类数,初始值为 0。
  2. 滑动窗口

    • 遍历数组 f,右边界 right 从 0 到 f.size()
      • 如果 hash[f[right]] 为 0,说明这是一个新种类,kinds 增加 1。
      • 将当前元素 f[right] 的计数加 1。
      • 如果 kinds 大于 2,说明窗口内的不同元素超过两种,需要收缩左边界:
        • f[left] 的计数减 1。
        • 如果 hash[f[left]] 为 0,说明这个种类已经完全移出窗口,kinds 减少 1。
        • 左边界 left 右移。
      • 更新 ret 为当前窗口的最大长度,即 right - left + 1
  3. 返回结果

    • 返回 ret,即找到的最长子数组的长度。

 具体代码

  1. class Solution
  2. {
  3. public:
  4. int totalFruit(vector<int>& f)
  5. {
  6. int hash[100001] = { 0 }; // 记录每种水果的频次
  7. int ret = 0; // 记录最长子数组的长度
  8. for (int left = 0, right = 0, kinds = 0; right < f.size(); right++)
  9. {
  10. if (hash[f[right]] == 0)
  11. kinds++; // 新出现的水果种类
  12. hash[f[right]]++;
  13. while (kinds > 2) // 如果窗口中有超过两个不同种类的水果,收缩左边界
  14. {
  15. hash[f[left]]--;
  16. if (hash[f[left]] == 0)
  17. kinds--; // 如果某种水果完全移除,减少种类计数
  18. left++;
  19. }
  20. ret = max(ret, right - left + 1); // 更新结果
  21. }
  22. return ret; // 返回结果
  23. }
  24. };

找到字符串中所有字母异位词(原题链接)

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

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

解题思路

目标是找到字符串 s 中所有与字符串 p 具有相同字符的排列(即找出所有的字母异位词)。该问题可以使用滑动窗口的方法来解决。我们使用两个哈希数组分别记录 p 的字符频率和当前窗口中字符的频率,然后通过滑动窗口来找到符合条件的子串。

步骤说明

  1. 初始化

    • hash1 用于记录字符串 p 中每个字符的频率。
    • hash2 用于记录当前滑动窗口中每个字符的频率。
    • m 为字符串 p 的长度,用于确定窗口大小。
    • ret 用于存储结果,即符合条件的起始位置。
  2. 初始化 hash1

    • 遍历字符串 p,更新 hash1 中每个字符的频率。
  3. 滑动窗口

    • right 从 0 到 s.size() 遍历字符串 s,扩展窗口右边界。
    • 更新 hash2 中当前字符的频率,并根据字符频率更新计数器 count
    • 如果当前窗口大小超过了 m,收缩左边界:
      • 更新 hash2 中移出字符的频率,并调整 count
    • 如果 count 等于 m,说明当前窗口中的字符排列符合要求,将左边界的索引加入结果 ret
  4. 返回结果

    • 返回结果 ret,包含所有符合条件的起始位置。

 具体代码

  1. class Solution
  2. {
  3. public:
  4. vector<int> findAnagrams(string s, string p)
  5. {
  6. vector<int> ret; // 用于存储结果
  7. int hash1[26] = { 0 }; // 记录字符串 p 中每个字符的频率
  8. for (auto ch : p)
  9. hash1[ch - 'a']++; // 更新 hash1
  10. int hash2[26] = { 0 }; // 记录当前窗口中每个字符的频率
  11. int m = p.size(); // 字符串 p 的长度
  12. for (int left = 0, right = 0, count = 0; right < s.size(); right++)
  13. {
  14. char in = s[right];
  15. if (++hash2[in - 'a'] <= hash1[in - 'a'])
  16. count++; // 更新字符计数
  17. if (right - left + 1 > m) // 如果当前窗口大小超过 m,收缩窗口
  18. {
  19. char out = s[left++];
  20. if (hash2[out - 'a']-- < hash1[out - 'a'])
  21. count--; // 更新字符计数
  22. }
  23. if (count == m) // 如果计数等于 m,说明窗口中的字符排列符合要求
  24. ret.push_back(left); // 记录结果
  25. }
  26. return ret; // 返回结果
  27. }
  28. };

串联所有单词的子串(原题链接)

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

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

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

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

 

解题思路

目的是找到字符串 s 中所有包含 words 中所有单词的子串的位置,其中每个单词的长度相同,并且每个单词的出现次数也与 words 中的出现次数一致。该问题可以使用滑动窗口的方法解决,通过尝试所有可能的起始位置,并维护一个窗口来检查包含的单词是否符合条件。

步骤说明

  1. 初始化

    • hash1 用于记录 words 中每个单词的频次。
    • len 为每个单词的长度。
    • m 为单词的总数。
  2. 滑动窗口的起始位置

    • 遍历 i 从 0 到 len-1,尝试所有可能的起始位置。
  3. 维护窗口

    • 定义 hash2 用于记录当前窗口中每个单词的频次。
    • 初始化左右边界 leftright,并设置 count 用于记录窗口中符合条件的单词数。
    • 右边界 righti 开始,按单词长度递增,确保窗口内的单词都是长度一致的。
  4. 进出窗口操作

    • 进窗口
      • 提取当前右边界的单词 in,更新 hash2 中的频次,并根据 hash1 更新 count
    • 出窗口
      • 如果窗口大小超过 len * m,移除左边界的单词 out,更新 hash2count,并移动左边界。
    • 更新结果
      • 如果 count 等于 m,说明窗口中包含的单词与 words 中的单词完全匹配,记录左边界的索引。
  5. 返回结果

    • 返回记录的结果 ret,包含所有符合条件的起始位置。

 具体代码

  1. class Solution
  2. {
  3. public:
  4. vector<int> findSubstring(string s, vector<string>& words)
  5. {
  6. vector<int> ret; // 结果向量
  7. unordered_map<string, int> hash1; // 记录 words 中单词的频次
  8. for (auto& s : words)
  9. hash1[s]++; // 初始化 hash1
  10. int len = words[0].size(); // 单词长度
  11. int m = words.size(); // 单词总数
  12. for (int i = 0; i < len; i++) // 尝试所有可能的起始位置
  13. {
  14. unordered_map<string, int> hash2; // 记录当前窗口中单词的频次
  15. for (int left = i, right = i, count = 0; right + len <= s.size();
  16. right += len) {
  17. // 进窗口 + 维护 count
  18. string in = s.substr(right, len);
  19. hash2[in]++;
  20. if (hash1.count(in) && hash2[in] <= hash1[in])
  21. count++;
  22. // 判断
  23. if (right - left + 1 > len * m)
  24. {
  25. // 出窗口 + 维护 count
  26. string out = s.substr(left, len);
  27. if (hash1.count(out) && hash2[out] <= hash1[out])
  28. count--;
  29. hash2[out]--;
  30. left += len;
  31. }
  32. // 更新结果
  33. if (count == m)
  34. ret.push_back(left); // 记录符合条件的起始位置
  35. }
  36. }
  37. return ret; // 返回结果
  38. }
  39. };

最小覆盖子串(原题链接)

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

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

 

解题思路

目的是找到字符串 s 中包含字符串 t 的所有字符(包括重复字符)的最小子串。这个问题可以使用滑动窗口方法来高效解决。通过维护一个窗口来记录当前子串的字符频率,并确保窗口包含 t 中的所有字符,最终找到符合条件的最小子串。

步骤说明

  1. 初始化

    • hash1 用于记录字符串 t 中每个字符的频次。
    • kinds 记录 t 中有效字符的种类数(即有多少种不同的字符)。
    • hash2 用于记录当前窗口中每个字符的频次。
    • minlenbegin 用于记录最小子串的长度和起始位置,初始化为无效值。
  2. 记录 t 中的字符频次

    • 遍历字符串 t,更新 hash1 并记录有效字符的种类数 kinds
  3. 滑动窗口

    • right 从 0 到 s.size(),遍历字符串 s
      • 将当前右边界的字符加入窗口,更新 hash2count(记录符合条件的字符种类数)。
    • 判断窗口是否符合条件
      • 当窗口内的字符种类数等于 kinds 时,窗口符合条件。
      • 更新 minlenbegin,记录最小子串的长度和起始位置。
    • 收缩窗口
      • 移动左边界 left,更新 hash2count,直到窗口不再符合条件。
  4. 返回结果

    • 根据 beginminlen 返回最小子串。如果未找到符合条件的子串,返回空字符串。

 具体代码

  1. class Solution
  2. {
  3. public:
  4. string minWindow(string s, string t)
  5. {
  6. int hash1[128] = { 0 }; // 统计字符串 t 中每个字符的频次
  7. int kinds = 0; // 统计有效字符有多少种
  8. for (auto ch : t)
  9. if (hash1[ch]++ == 0)
  10. kinds++; // 记录每种字符的频次
  11. int hash2[128] = { 0 }; // 统计窗口内每个字符的频次
  12. int minlen = INT_MAX, begin = -1; // 初始化最小长度和起始位置
  13. for (int left = 0, right = 0, count = 0; right < s.size(); right++)
  14. {
  15. char in = s[right];
  16. if (++hash2[in] == hash1[in])
  17. count++; // 进窗口 + 维护 count
  18. while (count == kinds) // 判断条件
  19. {
  20. if (right - left + 1 < minlen) // 更新结果
  21. {
  22. minlen = right - left + 1;
  23. begin = left;
  24. }
  25. char out = s[left++];
  26. if (hash2[out]-- == hash1[out])
  27. count--; // 出窗口 + 维护 count
  28. }
  29. }
  30. if (begin == -1)
  31. return ""; // 如果没有符合条件的子串,返回空字符串
  32. else
  33. return s.substr(begin, minlen); // 返回最小子串
  34. }
  35. };
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/1007085
推荐阅读
相关标签
  

闽ICP备14008679号