学习内容

滑动窗口LeeCodeJava

滑动窗口模板

代码

  1. def findSubstring(s):
  2.     N = len(s) # 数组/字符串长度
  3.     left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
  4.     counter = collections.Counter() # 用于统计 子数组/子区间 是否有效
  5.     res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
  6.     while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
  7.         counter[s[right]] += 1 # 增加当前右边指针的数字/字符的计数
  8.         while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
  9.             counter[s[left]] -= 1 # 移动左指针前需要从counter中减少left位置字符的计数
  10.             left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
  11.         # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
  12.         res = max(res, right - left + 1) # 需要更新结果
  13.         right += 1 # 移动右指针，去探索新的区间
  14.     return res
  15. 作者：fuxuemingzhu
  16. 链接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers/solution/cong-zui-jian-dan-de-wen-ti-yi-bu-bu-tuo-7f4v/
  17. 来源：力扣（LeetCode）
  18. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路

滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：

定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 counter 用来统计该区间内的各个字符出现次数；
第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的计数；
第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动前，需要减少 left 指针的计数；
在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
right 指针每次向右移动一步，开始探索新的区间。

992.K个不同整数的数组

我的思路

通过HashSet来计算在某个数组内部不同的数字数量,然后通过双指针来框选区间,每个不同的区间可以分别计数,但是我对于双指针来框选的方式不明白.

消化题解的思路

需要使用3指针的思想来做,将区间中的不同数字的数量为K,,与数量为K-1的数字进行比较,长度差就是这一组的子数组数量.

567.字符串的排列

我的思路

使用标准的右侧指针,牵引左侧指针移动的方法.即先判断字符串的总数达到要求,随后判断需要缩减多少才能让要求符合,但是最后失败了,因为没考虑字串的排列必须要连续,导致了失败.

消化题解的思路

思考得过于复杂了,只需要维护两个固定长度的窗口的存在即可.然后平移这个窗口,逐个判断即可.

我的代码

  1. class Solution {
  2.     public boolean checkInclusion(String s1, String s2) {
  3.         if(s2.length()<s1.length()){return false;}
  4.         int[] target=new int[26];
  5.         int[] present=new int[26];
  6.         Arrays.fill(target,0);
  7.         Arrays.fill(present,0);
  8.         for (int i = 0; i < s1.length(); i++) {
  9.             ++target[s1.charAt(i)-'a'];
  10.             ++present[s2.charAt(i)-'a'];
  11.         }
  12.         int left=0;
  13.         int right=s1.length();
  14.         while (right<s2.length()){
  15.             if(Arrays.equals(target,present)){
  16.                 return true;
  17.             }
  18.             if(s2.charAt(left)!=s2.charAt(right)){
  19.                 --present[s2.charAt(left)-'a'];
  20.                 ++present[s2.charAt(right)-'a'];
  21.             }
  22.             ++left;
  23.             ++right;
  24.         }
  25.         return Arrays.equals(target, present);
  26.     }
  27. }