滑动窗口
相同知识点类型题见Github
过例子 长度最小的子数组
先用这一道题来过一下例子
想象一个管道,元素可以从头进入,可以从尾部出去。
每一个元素进入后,我们都可以计算管道里面元素是否符合当前的要求
如果符合,记录下当前的状态
如果不符合,看是否需要将最先进入的元素取出。
对于此题,所有元素均为正整数,新加入的元素总会让管道里元素之和保持不变或者变大,同时题目要求的是长度最小的字数组,所以在判断过程中需要记录管道内元素的个数。
如果某时刻管道内元素大于target,需要将最前面的元素取出,并判断此时是否满足大于等于target的要求
若满足
记录管道内元素个数,重复执行上一步,直到管道内元素之后小于target
若不满足
则继续添加新的元素,再判断是否满足大于等于target
public int minSubArrayLen(int target, int[] nums) {
int res=Integer.MAX_VALUE;
int sum=0;
int l=0;
for (int right = 0; right < nums.length; right++) {
sum=sum+nums[right];
while(sum>=target) {
res = Math.min( right-l+1, res );
sum = sum - nums[l++];
}
}
return res==Integer.MAX_VALUE ? 0 : res;
}
例子解析:
2 3 1 2 4 3
【2】 < 7
r++ l=1
继续
【2+3】 < 7
r++ r=2
继续
【2+3+1】 〈7
r++ r=3
继续
【2+3+1+2】 =8 〉7
超了
res = Math.min( right-l+1, res );
不断减去最前面的元素,直到其小于target
减去 arr[l] 此时l=0 , arr[0]=2
2【3+1+2】=6〈7
l++ l=1
2【3+1+2+4】= 10>7
r++ r=4
res = Math.min( right-l+1, res );
不断减去最前面的元素,直到其小于target
减去 arr[l] 此时l=1 arr[1]=3
l++ l=2
2 3 【1+2+4】 = 7 =7
res = Math.min( right-l+1, res );
不断减去最前面的元素,直到其小于target
减去 arr[l] 此时l=2 arr[2]=1
l++ l=2
2 3 【2+4+3】=9>7
r++ r=5
res = Math.min( right-l+1, res );
不断减去最前面的元素,直到其小于target
减去 arr[l] 此时l=3 arr[2]=2
l++ l=4
2 3 2 【4+3】=7=7
res = Math.min( right-l+1, res );
不断减去最前面的元素,直到其小于target
减去 arr[l] 此时l=4 arr[4]=4
2 3 2 4 【3】<7
且此时r 到达数组末尾,退出循环
438. 找到字符串中所有字母异位词
/**
* [438. 找到字符串中所有字母异位词 (mid)](https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/)
* @param s
* @param p
* @return
* 参考 https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/gong-shui-san-xie-shuang-zhi-zhen-shi-xi-t5hc/
*/
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int []c1=new int[26];
int []c2=new int[26];
int l=0;
for(int i=0;i<p.length();i++){
c2[p.charAt(i)-'a']++;
}
for(int r=0 ;r<s.length();r++){
c1[s.charAt(r)-'a']++;
// 如果 l到r 之间的距离超过了 p 的长度,就将最前面的字符频率-1
if((r+1-l)>p.length()) {
c1[s.charAt(l++)-'a']--;
}
if(check(c1,c2)){
res.add(l);
}
}
return res;
}
private Boolean check( int[] c1, int[] c2 ) {
for ( int i = 0; i < c1.length; i++ ) {
if(c1[i]!=c2[i])return false;
}
return true;
}
例子解析
/*
cbaebac
abc
c1 [ c 1]
c2 [ a 1 b 1 c 1]
r=0
c1 [ c 1 b 1 ]
c2 [ a 1 b 1 c 1]
r=1
c1 [ c 1 b 1 a 1]
c2 [ a 1 b 1 c 1]
r=2
r+1-l = 3 = p.length
进入check return true
left=0
res.add(left=0)
cbaebac
abc
c1 [ c 1 b 1 a 1 e 1]
c2 [ a 1 b 1 c 1]
r=3
r+1-l = 4 > p.length
将s的left 位置的字符频率-1
此时left = 0
c1 [ c 0 b 1 a 1 e 1]
l++ l=1
c1 [ c 0 b 2 a 1 e 1 ]
c2 [ a 1 b 1 c 1]
r=4
r+1-l = 4+1-1 > p.length
将s的left 位置的字符频率-1
此时left = 1
c1 [ c 0 b 1 a 1 e 1]
l++ l=2
cbaebac
abc
c1 [ c 0 b 1 a 2 e 1 ]
c2 [ a 1 b 1 c 1]
r=5
r+1-l = 5+1-2 > p.length
将s的left 位置的字符频率-1
此时left = 2
c1 [ c 0 b 1 a 1 e 1 ]
l++ l=3
c1 [ c 1 b 1 a 1 e 1 ]
c2 [ a 1 b 1 c 1]
r=6
r+1-l = 6+1-3 > p.length
将s的left 位置的字符频率-1
此时left = 3
c1 [ c 1 b 1 a 1 e 0 ]
l++ l=4
check return true
res.add(4)
*/