当前位置:   article > 正文

算法学习:双指针进阶之滑动窗口算法_双指针 滑窗

双指针 滑窗

 文章目录

  • 一、认识滑动窗口算法
  • 二、算法运用
    • 1.最小覆盖子串
    • 2.字符串排列
    • 3.找所有字母异位词
    • 4.最长无重复字串
  • 总结

一、认识滑动窗口算法

        本文讲的滑动窗口算法基于前面的基本的双指针技巧。在滑动窗口算法中,可以使用左右指针来记录窗口的左右边界,以及使用快慢指针来同时从两端向中间遍历数据流,从而加速算法的执行效率。滑动窗口算法的核心在于通过维护一个窗口来记录满足条件的数据,并在窗口移动的过程中更新窗口记录的结果,其时间复杂度为O(n)。具体来说,滑动窗口算法通常包括以下几个步骤:

  1. 初始化左右指针,表示窗口的左右边界。
  2. 移动右指针,扩大窗口,直到找到符合条件的窗口。
  3. 移动左指针,缩小窗口大小,直到不能再缩小为止。
  4. 在窗口移动的过程中,记录窗口的状态,例如最大值、最小值、子串长度等等。
  5. 返回窗口记录的结果。 

         下面是滑动窗口算法的核心框架:

  1. /* 滑动窗口算法框架 */
  2. void slidingWindow(String s) {
  3. // 用合适的数据结构记录窗口中的数据
  4. HashMap<Character, Integer> window = new HashMap<>();
  5. int left = 0, right = 0;
  6. while (right < s.length()) {
  7. // c 是将移入窗口的字符
  8. char c = s.charAt(right);
  9. window.put(c, window.getOrDefault(c, 0) + 1);
  10. // 增大窗口
  11. right++;
  12. // 进行窗口内数据的一系列更新
  13. ...
  14. /*** debug 输出的位置 ***/
  15. System.out.printf("window: [%d, %d)\n", left, right);
  16. /********************/
  17. // 判断左侧窗口是否要收缩
  18. while (left < right && window needs shrink) {
  19. // d 是将移出窗口的字符
  20. char d = s.charAt(left);
  21. window.put(d, window.get(d) - 1);
  22. // 缩小窗口
  23. left++;
  24. // 进行窗口内数据的一系列更新
  25. ...
  26. }
  27. }
  28. }

       

二、算法运用

1.最小覆盖子串

        下面选用力扣的第 76 题「最小覆盖子串」练习,详情请读者自动跳转至原题。

        该题的思路是建立need(记录目标个数)和window(记录当前窗口内满足条件的目标个数)两个计数器,通过扩大右窗口来找到可行解,而后通过缩小左窗口来找到最优解,直到右窗口到达数组的最右边。

代码如下(示例):

  1. class Solution {
  2. public String minWindow(String s, String t) {
  3. // 用于记录需要的字符和窗口中的字符及其出现的次数
  4. Map<Character,Integer> need = new HashMap<>();
  5. Map<Character,Integer> window = new HashMap<>();
  6. //计算字符串t中每个字符的出现次数,并将结果存储在need
  7. for(char c : t.toCharArray())
  8. need.put(c,need.getOrDefault(c,0)+1);//根据当前计数情况+1,首次出现则返回0并且+1
  9. int left=0,right=0;
  10. int valid =0;//窗口中满足的字符个数
  11. //记录最小覆盖子串的起始索引及长度
  12. int start=0,len=Integer.MAX_VALUE;
  13. //寻找可行解
  14. while(right<s.length()){
  15. //获取移入窗口的字符
  16. char c= s.charAt(right);
  17. //移右窗口
  18. right++;
  19. //窗口更新
  20. if(need.containsKey(c)){
  21. window.put(c,window.getOrDefault(c,0)+1);
  22. //valid记录目前满足的字符个数,直到找到可行解,前往下一步找到最优解
  23. if(window.get(c).equals(need.get(c)))
  24. valid++;
  25. }
  26. //找到可行解后通过移动左窗口找到最优解
  27. while(valid==need.size()){
  28. //更新最小覆盖子串
  29. if(right-left<len){
  30. start=left;
  31. len=right-left;
  32. }
  33. //获取移除窗口的字符
  34. char d = s.charAt(left);
  35. //移左窗口
  36. left++;
  37. //窗口更新
  38. if(need.containsKey(d)){
  39. //valid记录目前满足的字符个数,直到不再满足可行解,前往上一步再次移右窗口找到可行解
  40. if(window.get(d).equals(need.get(d)))
  41. valid--;
  42. window.put(d, window.get(d) - 1);
  43. }
  44. }
  45. }
  46. //返回最小覆盖子串
  47. return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
  48. }
  49. }

2.字符串的排列

       下面选用力扣的第 567 题「字符串的排列」练习,详情请读者自动跳转至原题。

        本题的解题思路也是运用到了滑动窗口算法,需要修改的地方在于题目要求的不同。本题要求S1的排列之一是S2的子串。也就是说S1存在S2,且这个子串不包含另外的其他字符,不同于第一题。本题需要注意以下几点:

1.判断是否要缩小左窗口在于整个窗口长度是否大于S2本身

2.本题并不是要求寻找最优解,而是优先找到S2,所以当valid == need.size(),即满足条件要求,此时立即返回true,不必再次遍历完整个数组。

3.本意的可行解也不同于上面一题,这里的可行解以s1本身的长度为单位,也就是说当找到与s1相似的子串时,就开始判断窗口内的子串是否是s1

代码如下(示例):

  1. class Solution {
  2. public boolean checkInclusion(String s1, String s2) {
  3. // 用于记录需要的字符和窗口中的字符及其出现的次数
  4. Map<Character,Integer> need = new HashMap<>();
  5. Map<Character,Integer> window = new HashMap<>();
  6. //计算字符串t中每个字符的出现次数,并将结果存储在need
  7. for(int i =0; i<s1.length();i++){
  8. char c = s1.charAt(i);
  9. need.put(c,need.getOrDefault(c,0)+1);//根据当前计数情况+1,首次出现则返回0并且+1
  10. }
  11. int left=0,right=0;
  12. int valid=0;//窗口中满足的字符个数
  13. //寻找可行解
  14. while(right<s2.length()){
  15. //获取移入窗口的字符
  16. char c=s2.charAt(right);
  17. //移右窗口
  18. right++;
  19. //窗口更新
  20. if(need.containsKey(c)){
  21. //valid记录目前满足的字符个数,直到找到可行解
  22. window.put(c,window.getOrDefault(c,0)+1);
  23. if(window.get(c).equals(need.get(c)))
  24. valid++;
  25. }
  26. //找到可行解后通过移动左窗口找到S1
  27. while(right-left>=s1.length()){
  28. //成功找到S1
  29. if(valid==need.size())
  30. return true;
  31. //获取移除窗口的字符
  32. char d=s2.charAt(left);
  33. //缩小窗口
  34. left++;
  35. //窗口更新
  36. if(need.containsKey(d)){
  37. //valid记录目前满足的字符个数,直到不再满足可行解,前往上一步再次移右窗口找到可行解
  38. if(window.get(d).equals(need.get(d)))
  39. valid--;//
  40. //减少d字符在窗口记录中的次数
  41. window.put(d,window.get(d) - 1);
  42. }
  43. }
  44. }
  45. //未找到S1
  46. return false;
  47. }
  48. }

3.找所有字母异位词

       下面选用力扣的第 438 题「找到字符串中所有字母异位词」练习,详情请读者自动跳转至原题。

        该题的基本思路和上一题相同,本质就是排列。不同点在于本题要求返回所有满足条件的结果集,这里用到了List<Integer> res = new ArrayList<>();来存结果集。

代码如下(示例):

  1. class Solution {
  2. public List<Integer> findAnagrams(String s, String p) {
  3. // 用于记录需要的字符和窗口中的字符及其出现的次数
  4. Map<Character,Integer> need = new HashMap<>();
  5. Map<Character,Integer> window = new HashMap<>();
  6. //计算字符串p中每个字符的出现次数,并将结果存储在need
  7. for(char c: p.toCharArray())
  8. need.put(c,need.getOrDefault(c,0)+1);//根据当前计数情况+1,首次出现则返回0并且+1
  9. int left=0,right=0;
  10. int valid=0;//窗口中满足的字符个数
  11. List<Integer> res = new ArrayList<>();//把符合条件的起始索引存到集合中
  12. //寻找可行解
  13. while(right<s.length()){
  14. char c =s.charAt(right);
  15. right++;
  16. //窗口更新
  17. if(need.containsKey(c)){
  18. //valid记录目前满足的字符个数,直到找到可行解
  19. window.put(c,window.getOrDefault(c,0)+1);
  20. if(window.get(c).equals(need.get(c)))
  21. valid++;
  22. }
  23. //找到可行解后通过移动左窗口找到p的异位词
  24. while(right-left>=p.length()){
  25. if(valid==need.size())
  26. res.add(left);//将索引插入集合中
  27. char d =s.charAt(left);
  28. left++;
  29. //窗口更新
  30. if(need.containsKey(d)){
  31. //valid记录目前满足的字符个数,直到不再满足可行解,前往上一步再次移右窗口找到可行解
  32. if(window.get(d).equals(need.get(d)))
  33. valid--;
  34. window.put(d,window.get(d)-1);
  35. }
  36. }
  37. }
  38. //返回所有结果集
  39. return res;
  40. }
  41. }

3.最长无重复子串

       下面选用力扣的第 3 题「无重复字符的最长子串」练习,详情请读者自动跳转至原题。

        该题也是套用滑动窗口算法。本题要考虑的地方比前面要少,在这里要求找到最长的无重复子串,并返回其长度。所以,我们并不需要考虑建立一个need表来比较,同时valid也就不需要了。我们只需要记录窗口中每个字符的个数,当window.get(c)>1时,也就是说窗口内的字串出现了重复项。此时,我们需要当窗口内这个重复的字符移除后,才能更新len(用来记录字符串的长度),这里我们还用到了len = Math.max(len, right-left)来记录结果集中的最大值。

代码如下(示例):

  1. class Solution {
  2. public int lengthOfLongestSubstring(String s) {
  3. //用来记录窗口内各个字符的个数
  4. Map<Character,Integer> window = new HashMap<>();
  5. int left=0,right=0;
  6. int len=0;//记录最长子串长度
  7. //找到可行解
  8. while(right<s.length()){
  9. char c= s.charAt(right);
  10. right++;
  11. //更新窗口
  12. window.put(c,window.getOrDefault(c,0)+1);
  13. //此时找到重复项,并将其移除
  14. while(window.get(c)>1){
  15. char d = s.charAt(left);
  16. left++;
  17. window.put(d,window.getOrDefault(d,0)-1);
  18. }
  19. //记录最大长度
  20. len = Math.max(len, right - left);
  21. }
  22. return len;
  23. }
  24. }


总结

        滑动窗口算法基于左右指针和快慢指针的基础上,其主要应用于字符串排列的判断,相较于仅仅使用双指针,效率会更高。其特点在于创造了计数器,再加上窗口移动(指针移动)。在字符串排列判断这一类型上优先选择滑动窗口算法。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/1006520
推荐阅读
相关标签
  

闽ICP备14008679号