滑动窗口模块
滑动窗口类问题:总能找到一个窗口,从前往后移动来查找结果值。
这个窗口的大小可能是固定的,也可能是变化的。但窗口的大小一定是有限的。
https://www.cnblogs.com/huansky/p/13488234.html
Leetcode 3. 无重复字符的最长子串
题意理解:
给定一个字符串
s
,请你找出其中不含有重复字符的 最长子串 的长度。我们采用滑动窗口来解决这道问题,其中:滑动窗口用来查找不重复子串。
解题思路:
找到一个位置i,开始扩展滑动窗口,len++,当出现重复元素时,记录不重复子串长度,i位置向后移一位。
1.滑动窗口解题
public int lengthOfLongestSubstring(String s) {
int maxLen=0;
HashSet<Character> set=new HashSet<>();
for(int i=0;i<s.length();i++){
int j=i;
while(j<s.length()&&(!set.contains(s.charAt(j)))){
set.add(s.charAt(j));
j++;
}
maxLen=Math.max(maxLen,set.size());
set=new HashSet<>();
}
return maxLen;
}
2.复杂度分析
时间复杂度:O(n^2),遍历元素和遍历滑动窗口的时间耗费
空间复杂度:O(n), 所有set的空间损耗。
Leetcode 438. 找到字符串中所有字母异位词
题意理解:
给定两个字符串
s
和p
,找到s
中所有p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
给定一个目标字符串p,在字符串s中寻找其异位词的位置下标。
则s中存在和p相同长度的子串,且子串的组成相同,返回该子串的位置即可。
此处采用滑动窗口来解题。
解题思路:
采用滑动窗口解题,其中窗口大小等于p的长度
将窗口从0下标开始向后移动,每次取窗口里的子串进行判断
窗口子串是否是p的异位词
是怎将窗口位置下标加入结果集,否则不加入
将窗口继续向后移动。
1.滑动窗口解题
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result=new ArrayList<>();
int window=p.length();
for(int i=0;i<s.length()-window+1;i++){
String str=s.substring(i,i+window);
if(isAllotopicWord(str,p)){
result.add(i);
}
}
return result;
}
public boolean isAllotopicWord(String str,String target){
int[] letter=new int[26];
for(int i=0;i<str.length();i++)
letter[str.charAt(i)-'a']+=1;
for(int i=0;i<target.length();i++)
letter[target.charAt(i)-'a']-=1;
for(int i=0;i<letter.length;i++)
if(letter[i]!=0) return false;
return true;
}
2.复杂度分析
时间复杂度:O(n^2)
空间复杂度:O(n)
子串模块
子串:
子串类题目通常解决方法有:滑动窗口、双指针等
特别要注意一些边界判断,容易出错
再就是如何优化时间|空间复杂度。
Leetcode 560. 和为 K 的子数组
题意理解:
给你一个整数数组
nums
和一个整数k
,请你统计并返回 该数组中和为k
的子数组的个数 。子数组是数组中元素的连续非空序列。查找有多少个连续的子序列和为k。是子串遍历的一类问题。
解题思路:
遍历所有的连续子串,若子串长度==k,则result++
特别的注意:
当子串和大于k时,不代表遍历停止,后续的负数可能使其仍然满足一个子串。
如:1,-1,0
k=0
则满足规则的子串有: 1,-1 1,-1,0 0
1.子串遍历解题
public int subarraySum(int[] nums, int k) {
int result=0;
for(int i=0;i<nums.length;i++){
int sum=0;
for(int j=i;j<nums.length;j++){
sum+=nums[j];
if(sum==k) result++;
}
}
return result;
}
2.复杂度分析
时间复杂度:O(n^2)
空间复杂度:O(1)
Leetcode 239. 滑动窗口最大值
题意理解:
给你一个整数数组
nums
,有一个大小为k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k
个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。解题思路:
选中一个1起始位置,如0, 则获得第一个滑动窗口: 1,3 ,-1 此时max=3
向下滑动一个位置,此时要有一个数加入,一个数被丢弃
使用队列来维持窗口中的最大值。使最大值总是出现在队列尾端。
比最大值小的值维护在,队首。
这道题目的难点在于:最大的数被移出窗口后,如何从剩下的值中获得最大值
还一个点:(关键)
- k个数的数列,其中包含最大值x,则x以前的数是没有意义的:
- 因为只要能取到x, 一定不会取到x之前的数,因为x最为max,一定比前面的值大
- 除此之外:
- 新进入的值y: y前面比它小的值也是没有意义的,若y比x大,则y前面所有的值都是没有意义的废数。
这样的解法本质上是将滑动窗口里的值维护到了一个单调队列里,他总是保持最大值及到当前位置的比它小的值,最大值前面且比它小的数是废数。
1.滑动窗口解题
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length==1||k==1){
return nums;
}
Deque<Integer> queue=new LinkedList<>();
List<Integer> numbers=new ArrayList<>();
for(int i=0;i<nums.length;i++){
//弹出过期数据
if((!queue.isEmpty())&&queue.peekFirst()==i-k){
queue.pollFirst();
}
//前面比它大
if(queue.isEmpty()){
queue.offerLast(i);
} else if(nums[queue.peekLast()]>nums[i]) {
queue.offerLast(i);
}else if(nums[queue.peekLast()]<=nums[i]){
//前面比它小,全部弹出
while((!queue.isEmpty())&&nums[queue.peekLast()]<=nums[i]){
queue.pollLast();
}
queue.offerLast(i);
}
if(i>=k-1){
numbers.add(queue.peekFirst());
}
}
int[] result=new int[numbers.size()];
for(int i=0;i<numbers.size();i++){
result[i]=nums[numbers.get(i)];
}
return result;
}
}
2.复杂度分析
时间复杂度:O(n)
空间复杂度:O(n)
Leetcode 76. 最小覆盖子串
题意理解:
给你一个字符串
s
、一个字符串t
。返回s
中涵盖t
所有字符的最小子串。如果s
中不存在涵盖t
所有字符的子串,则返回空字符串""
。注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。如果
s
中存在这样的子串,我们保证它是唯一的答案及返回s中包含t所有元素的最短子串。此处还是可以用双指针来解决这道题目。
解题思路:
1.找到一个左指针开头: 即一个t中的元素开头。
2.找到一个右指针结尾: 即一个t中的元素结尾,且当前滑动窗口包含t中所有元素。
3.将结果维护在result串中
4.左指针向右移动,弹出左侧元素,直到左侧开始第一个t中元素
5.右指针扩展,右边找滑动窗口的结尾。
6.重复步骤3
一个要注意的点:如何判断s包含t所有元素呢?t中可能有重复元素
比较两个方面:是否右t中元素,s中的对应t中的元素个数要多于或等于t中对应元素的个数
如:s: abcab t:aab s中a的个数>=t中a的个数,才能满足条件:s包含t所有元素
上述方法没问题,但是会发生超时问题:优化
还是left和right两个指针
1.right向右拓展,left向right靠近,最终获得最短符合条件的子串
2.用sMap和tMap来维护子串和t串的元素及个数
3.判断tMap所有key满足:sMap.get(c)>tMap.get(c),则[left,right]子串满足要求
4.将结果子串用ansL和ansR维护,其中表示子串的最左位置和最右位置
5.最后返回[ansL,ansR]子串
优化了哪里:
sMap由right和left实时维护,不用每次在对[left,right]统计,少了一层for循环
时间复杂度优化了
1.双指针解题
class Solution {
public String minWindow(String s, String t) {
int ansL=0,ansR=-1;
//保存t中元素及个数|s
Map<Character,Integer> tMap=new HashMap<>();
Map<Character,Integer> sMap=new HashMap<>();
for(char c:t.toCharArray()){
tMap.put(c,tMap.getOrDefault(c,0)+1);
}
int left=0,right=0;
while(right<s.length()){
if(tMap.containsKey(s.charAt(right)))
sMap.put(s.charAt(right),sMap.getOrDefault(s.charAt(right),0)+1);
while(left<=right&&isContains(sMap,tMap)){//right向右移动,left向right缩,最后获得最短子串
if(ansR==-1||right-left<ansR-ansL) {
ansL=left;
ansR=right;
}
if(tMap.containsKey(s.charAt(left))){
sMap.put(s.charAt(left),sMap.getOrDefault(s.charAt(left),0)-1);
}
left++;
}
right++;
}
return ansR-ansL+1<=0?"":s.substring(ansL,ansR+1);
}
//判断
public boolean isContains(Map<Character,Integer> sMap,Map<Character,Integer> tMap){
for(char key:tMap.keySet()){
if(tMap.get(key)>sMap.getOrDefault(key,0)) return false;
}
return true;
}
}
2.复杂度分析
时间复杂度:O(n^2)
空间复杂度:O(n)
这道题是一道困难题:难在容易超时。如何对代码优化。