devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

有了这个解题模板，面试高频滑动窗口问题 so easy ！

作者：凡人多烦事01 | 2024-03-21 00:10:15

赞

踩

最长无重复字串 吴师兄

作者：P.yh

导语

滑动窗口类问题是面试当中的 高频题 ，问题本身其实并不复杂，但是实现起来细节思考非常的多，想着想着可能因为变量变化，指针移动等等问题，导致程序反复删来改去，有思路，但是程序写不出是这类问题最大的障碍。

本文会将 LeetCode 里面的大部分滑动窗口问题分析、总结、分类，并提供一个可以参考的模版，相信可以有效减少面试当中的算法实现部分的不确定性。

由于本文涉及的例题与代码较多，建议先收藏后再仔细阅读，相信你肯定能攻克 滑动窗口问题。

滑动窗口

滑动窗口这类问题一般需要用到 双指针 来进行求解，另外一类比较特殊则是需要用到特定的数据结构，像是 sorted_map。

后者有特定的题型，后面会列出来，但是，对于前者，题形变化非常的大，一般都是基于字符串和数组的，所以我们重点总结这种基于双指针的滑动窗口问题。

题目问法大致有这几种：

  • 给两个字符串，一长一短，问其中短的是否在长的中满足一定的条件存在，例如：
  • 求长的的最短子串，该子串必须涵盖短的的所有字符
  • 短的的 anagram 在长的中出现的所有位置
  • ...
  • 给一个字符串或者数组，问这个字符串的子串或者子数组是否满足一定的条件，例如：
  • 含有少于 k 个不同字符的最长子串
  • 所有字符都只出现一次的最长子串
  • ...

除此之外，还有一些其他的问法，但是不变的是，这类题目脱离不开主串（主数组）和子串（子数组）的关系，要求的时间复杂度往往是 O(n) ，空间复杂度往往是常数级的。

之所以是滑动窗口，是因为，遍历的时候，两个指针一前一后夹着的子串（子数组）类似一个窗口，这个窗口大小和范围会随着前后指针的移动发生变化。


v2-4aea3560984a2f908001cd3802d90b3e_b.jpg


解题思路与模板

根据前面的描述，滑动窗口就是这类题目的重点，换句话说，窗口的移动 就是重点！

我们要控制前后指针的移动来控制窗口，这样的移动是有条件的，也就是要想清楚在什么情况下移动，在什么情况下保持不变。

我的思路是保证右指针每次往前移动一格，每次移动都会有新的一个元素进入窗口，这时条件可能就会发生改变，然后根据当前条件来决定左指针是否移动，以及移动多少格。

我写来一个模版在这里，可以参考：

        
  1. //authour:P.yh
  2. //Editor:程序员小吴
  3. public int slidingWindowTemplate(String[] a, ...) {
  4.     // 输入参数有效性判断
  5.     if (...) {
  6.         ...
  7.     }
  8.  
  9.     // 申请一个散列，用于记录窗口中具体元素的个数情况
  10.     // 这里用数组的形式呈现，也可以考虑其他数据结构
  11.     int[] hash = new int[...];
  12.  
  13.     // 预处理(可省), 一般情况是改变 hash
  14.     ...
  15.  
  16.     // l 表示左指针
  17.     // count 记录当前的条件，具体根据题目要求来定义
  18.     // result 用来存放结果
  19.     int l = 0, count = ..., result = ...;
  20.     for (int r = 0; r < A.length; ++r) {
  21.         // 更新新元素在散列中的数量
  22.         hash[A[r]]--;
  23.  
  24.         // 根据窗口的变更结果来改变条件值
  25.         if (hash[A[r]] == ...) {
  26.             count++;
  27.         }
  28.  
  29.         // 如果当前条件不满足，移动左指针直至条件满足为止
  30.         while (count > K || ...) {
  31.             ...
  32.             if (...) {
  33.                 count--;
  34.             }
  35.             hash[A[l]]++;
  36.             l++;
  37.         }
  38.  
  39.         // 更新结果
  40.         results = ...
  41.     }
  42.  
  43.     return results;
  44. }

这里面的 “移动左指针直至条件满足” 部分，需要具体题目具体分析，其他部分的变化不大。

具体题目分析与代码

1. 找到字符串中所有字母异位词

题目来源于 LeetCode 上第 438 号问题：找到字符串中所有字母异位词。题目难度为 Easy，目前通过率为 43.6% 。

题目描述

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100 。

题目解析

别看这是一道 easy 难度的题目，如果限定你在 O(n) 时间复杂度内实现呢？

按照模版会很简单！

首先窗口是固定的，窗口长度就是输入参数中第二个字符串的长度，也就是说，右指针移动到某个位置后，左指针必须跟着一同移动，且每次移动都是一格，模版中 count 用来记录窗口内满足条件的元素，直到 count 和窗口长度相等即可更新答案。

代码实现

        
  1. // 使用上面的模板进行解题，so easy ！
  2. public List<Integer> findAnagrams(String s, String p) {
  3.     // 输入参数有效性判断
  4.     if (s.length() < p.length()) {
  5.         return new ArrayList<Integer>();
  6.     }
  7.  
  8.     // 申请一个散列，用于记录窗口中具体元素的个数情况
  9.     // 这里用数组的形式呈现，也可以考虑其他数据结构
  10.     char[] sArr = s.toCharArray();
  11.     char[] pArr = p.toCharArray();
  12.  
  13.     int[] hash = new int[26];
  14.  
  15.     for (int i = 0; i < pArr.length; ++i) {
  16.         hash[pArr[i] - 'a']++;
  17.     }
  18.  
  19.     // l 表示左指针
  20.     // count 记录当前的条件，具体根据题目要求来定义
  21.     // result 用来存放结果
  22.     List<Integer> results = new ArrayList<>();
  23.     int l = 0, count = 0, pLength = p.length();
  24.  
  25.     for (int r = 0; r < sArr.length; ++r) {
  26.         // 更新新元素在散列中的数量
  27.         hash[sArr[r] - 'a']--;
  28.  
  29.         // 根据窗口的变更结果来改变条件值
  30.         if (hash[sArr[r] - 'a'] >= 0) {
  31.             count++;
  32.         }
  33.  
  34.         // 如果当前条件不满足，移动左指针直至条件满足为止
  35.         if (r > pLength - 1) {
  36.             hash[sArr[l] - 'a']++;
  37.  
  38.             if (hash[sArr[l] - 'a'] > 0) {
  39.                 count--;
  40.             }
  41.  
  42.             l++;
  43.         }
  44.  
  45.         // 更新结果
  46.         if (count == pLength) {
  47.             results.add(l);
  48.         }
  49.     }
  50.  
  51.     return results;
  52. }

2. 最小覆盖子串

题目来源于 LeetCode 上第 76 号问题：最小覆盖子串。题目难度为 Hard，目前通过率为 35.8% 。

题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例： 

        
  1. 输入: S = "ADOBECODEBANC", T = "ABC"
  2. 输出: "BANC"

题目解析

同样是两个字符串之间的关系问题，因为题目求的最小子串，也就是窗口的最小长度，说明这里的窗口大小是可变的，这里移动左指针的条件变成，只要左指针指向不需要的字符，就进行移动。

依旧使用上面的模板解题！

代码实现

        
  1. // 使用上面的模板进行解题，受篇幅限制下面的代码就不添加注释了
  2. public String minWindow(String s, String t) {
  3.     if (s.length() < t.length()) {
  4.         return "";
  5.     }
  6.  
  7.     char[] sArr = s.toCharArray();
  8.     char[] tArr = t.toCharArray();
  9.  
  10.     int[] hash = new int[256];
  11.  
  12.     for (int i = 0; i < tArr.length; ++i) {
  13.         hash[tArr[i]]++;
  14.     }
  15.  
  16.     int l = 0, count = tArr.length, max = s.length() + 1;
  17.     String result = "";
  18.     for (int r = 0; r < sArr.length; ++r) {
  19.         hash[sArr[r]]--;
  20.  
  21.         if (hash[sArr[r]] >= 0) {
  22.             count--;
  23.         }
  24.  
  25.         while (l < r && hash[sArr[l]] < 0) {
  26.             hash[sArr[l]]++;
  27.             l++;
  28.         }
  29.  
  30.         if (count == 0 && max > r - l + 1) {
  31.             max = r - l + 1;
  32.             result = s.substring(l, r + 1);
  33.         }
  34.     }
  35.  
  36.     return result;
  37. }

3. 无重复字符的最长子串

题目来源于 LeetCode 上第 3 号问题：无重复字符的最长子串。题目难度为 Medium，目前通过率为 29.0% 。

题目描述

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

示例 1: 

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

题目解析

输入只有一个字符串，要求子串里面不能够有重复的元素，这里 count 都不需要定义，直接判断哈希散列里面的元素是不是在窗口内即可，是的话得移动左指针去重。

具体操作如下：

建立一个 256 位大小的整型数组 freg ，用来建立字符和其出现位置之间的映射。

维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

  • （1）如果当前遍历到的字符从未出现过，那么直接扩大右边界；
  • （2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；
  • （3）重复（1）（2），直到左边索引无法再移动；
  • （4）维护一个结果 res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果。

动画描述


v2-1d671c551571210a6bb3a71abae85815_b.gif


代码实现

        
  1. public int lengthOfLongestSubstring(String s) {
  2.     if (s == null || s.length() == 0) {
  3.         return 0;
  4.     }
  5.  
  6.     char[] sArr = s.toCharArray();
  7.     int[] hash = new int[256];
  8.  
  9.     int l = 0, result = 1;
  10.     for (int r = 0; r < sArr.length; ++r) {
  11.         hash[sArr[r]]++;
  12.  
  13.         while (hash[sArr[r]] != 1) {
  14.             hash[sArr[l]]--;
  15.             l++;
  16.         }
  17.  
  18.         result = Math.max(result, r - l + 1);
  19.     }
  20.  
  21.     return result;
  22. }

4. 字符串的排列

题目来源于 LeetCode 上第 567 号问题：字符串的排列。题目难度为 Medium，目前通过率为 31.8% 。

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1: 

        
  1. 输入: s1 = "ab" s2 = "eidbaooo"
  2. 输出: True
  3. 解释: s2 包含 s1 的排列之一 ("ba").

示例2: 

        
  1. 输入: s1= "ab" s2 = "eidboaoo"
  2. 输出: False

题目解析

和 438 那题很类似，但是这里不需要记录答案了，有就直接返回 true。

代码实现

        
  1. public boolean checkInclusion(String s1, String s2) {
  2.     if (s1.length() > s2.length()) {
  3.         return false;
  4.     }
  5.  
  6.     char[] s1Arr = s1.toCharArray();
  7.     char[] s2Arr = s2.toCharArray();
  8.  
  9.     int[] hash = new int[26];
  10.  
  11.     for (int i = 0; i < s1Arr.length; ++i) {
  12.         hash[s1Arr[i] - 'a']++;
  13.     }
  14.  
  15.     int l = 0, count = 0;
  16.     for (int r = 0; r < s2Arr.length; ++r) {
  17.         hash[s2Arr[r] - 'a']--;
  18.  
  19.         if (hash[s2Arr[r] - 'a'] >= 0) {
  20.             count++;
  21.         }
  22.  
  23.         if (r >= s1Arr.length) {
  24.             hash[s2Arr[l] - 'a']++;
  25.  
  26.             if (hash[s2Arr[l] - 'a'] >= 1) {
  27.                 count--;
  28.             }
  29.  
  30.             l++;
  31.         }
  32.  
  33.         if (count == s1Arr.length) {
  34.             return true;
  35.         }
  36.     }
  37.  
  38.     return false;
  39. }

5. K 个不同整数的子数组

题目来源于 LeetCode 上第 992 号问题：字符串的排列。题目难度为 Hard，目前通过率为 26.4% 。

题目描述

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

示例 1： 

        
  1. 输出：A = [1,2,1,2,3], K = 2
  2. 输入：7
  3. 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2： 

        
  1. 输入：A = [1,2,1,3,4], K = 3
  2. 输出：3
  3. 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

题目解析

看完了字符串类型的题目，这次来看看数组类型的。

题目中的 subarray 已经明确了这个题可以考虑用滑动窗口，这题比较 trick 的一个地方在于，这里不是求最小值最大值，而是要你计数。

但是如果每次仅仅加 1 的话又不太对，例如 A = [1,2,1,2,3], K = 2 这个例子，假如右指针移到 index 为 3 的位置，如果按之前的思路左指针根据 count 来移动，当前窗口是 [1,2,1,2]，但是怎么把 [2,1] 给考虑进去呢？

可以从数组和子数组的关系来思考！

假如 [1,2,1,2] 是符合条件的数组，如果要计数的话，[1,2,1,2] 要求的结果是否和 [1,2,1] 的结果存在联系？这两个数组的区别在于多了一个新进来的元素，之前子数组计数没考虑到这个元素，假如把这个元素放到之前符合条件的子数组中组成的新数组也是符合条件的，我们看看这个例子中所有满足条件的窗口以及对应的满足条件的子数组情况：

        
  1. [1,2,1,2,3]  // 窗口满足条件
  2.  l r         // 满足条件的子数组 [1,2]
  3.  
  4. [1,2,1,2,3]  // 窗口满足条件
  5.  l   r       // 满足条件的子数组 [1,2],[2,1],[1,2,1]
  6.  
  7. [1,2,1,2,3]  // 窗口满足条件
  8.  l     r     // 满足条件的子数组 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2]
  9.  
  10. [1,2,1,2,3]  // 窗口不满足条件，移动左指针至满足条件
  11.  l       r   
  12.  
  13. [1,2,1,2,3]  // 窗口满足条件
  14.        l r   // 满足条件的子数组 [1,2],[2,1],[1,2,1],[1,2],[2,1,2],[1,2,1,2],[2,3]

你可以看到对于一段连续的数组，新的元素进来，窗口增加 1，每次的增量都会在前一次增量的基础上加 1。

当新的元素进来打破当前条件会使这个增量从新回到 1，这样我们左指针移动条件就是只要是移动不会改变条件，就移动，不然就停止。

代码实现

        
  1. public int subarraysWithKDistinct(int[] A, int K) {
  2.     if (A == null || A.length < K) {
  3.         return 0;
  4.     }
  5.  
  6.     int[] hash = new int[A.length + 1];
  7.  
  8.     int l = 0, results = 0, count = 0, result = 1;
  9.     for (int r = 0; r < A.length; ++r) {
  10.         hash[A[r]]++;
  11.  
  12.         if (hash[A[r]] == 1) {
  13.             count++;
  14.         }
  15.  
  16.         while (hash[A[l]] > 1 || count > K) {
  17.             if (count > K) {
  18.                 result = 1;
  19.                 count--;
  20.             } else {
  21.                 result++;
  22.             }
  23.             hash[A[l]]--;
  24.             l++;
  25.         }
  26.  
  27.         if (count == K) {
  28.             results += result;
  29.         }
  30.     }
  31.  
  32.     return results;
  33. }

6. 替换后的最长重复字符

题目来源于 LeetCode 上第 424 号问题：替换后的最长重复字符。题目难度为 Medium，目前通过率为 37.3% 。

题目描述

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

题目解析

这道题想 accept 的话不难，但是问题在于怎么知道当前窗口中数量最多的字符的数量，因为需要替换的字符就是当前窗口的大小减去窗口中数量最多的字符的数量。

最简单的方法就是把 哈希散列 遍历一边找到最大的字符数量，但是仔细想想如果我们每次新进元素都更新这个最大数量，且只更新一次，我们保存的是当前遍历过的全局的最大值，它肯定是比实际的最大值大的，我们左指针移动的条件是 r - l + 1 - maxCount > k，保存的结果是 result = Math.max(r - l + 1, result); 这里 maxCount 比实际偏大的话，虽然导致左指针不能移动，但是不会记录当前的结果，所以最后的答案并不会受影响。

代码实现

        
  1. public int characterReplacement(String s, int k) {
  2.     if (s == null || s.length() == 0) {
  3.         return 0;
  4.     }
  5.  
  6.     char[] sArr = s.toCharArray();
  7.  
  8.     int[] hash = new int[26];
  9.  
  10.     int l = 0, maxCount = 0, result = 0;
  11.     for (int r = 0; r < sArr.length; ++r) {
  12.         hash[sArr[r] - 'A']++;
  13.  
  14.         maxCount = Math.max(maxCount, hash[sArr[r] - 'A']);
  15.  
  16.         while (r - l + 1 - maxCount > k) {
  17.             hash[sArr[l] - 'A']--;
  18.             l++;
  19.         }
  20.  
  21.         result = Math.max(r - l + 1, result);
  22.     }
  23.  
  24.     return result;
  25. }

总结

受篇幅限制，本文仅列举了 6 道与滑动窗口有关的算法题，并且使用了固定的套路进行了分析与代码实现。

双指针类的滑动窗口问题思维复杂度并不高，但是出错点往往在细节。

记忆常用的解题模版还是很有必要的，特别是对于这种变量名多，容易混淆的题型。

有了这个框架，思考的点就转化为 “什么条件下移动左指针”，无关信息少了，思考加实现自然不是问题。


我的专栏：

和程序员小吴一起学算法


❤️ 看完三件事：

如果你觉得这篇内容对你挺有启发，我想邀请你帮我三个忙：

  1. 点赞，让更多的人也能看到这篇内容（收藏不点赞，都是耍流氓 -_-）
  2. 关注我和专栏，让我们成为长期关系
  3. 关注公众号「五分钟学算法」，第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。

v2-7d84a7f4361bd5f8d21b98b9edb0b1b4_b.jpg

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号