提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
前言
接下来就开始介绍数组操作中另一个重要的方法:滑动窗口。 所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
一、力扣209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int len = Integer.MAX_VALUE,count = 0;
int i,j;
for(i = 0, j = 0; j < nums.length;){
if(count >= target){
len = Math.min(len, j - i);
count -= nums[i];
i ++;
}else{
count += nums[j];
j ++;
}
}
while(count >= target){
len = Math.min(len, j - i);
count -= nums[i];
i ++;
}
return len == Integer.MAX_VALUE ? 0 : len;
}
}
二、力扣904. 水果成篮
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer,Integer> map = new HashMap<>();
int len = -1;
for(int i = 0, j = 0; j < fruits.length;){
if(map.size() <= 2){
map.put(fruits[j],map.getOrDefault(fruits[j],0)+1);
j ++;
if(map.size() <= 2){
len = Math.max(len,j-i);
}
}
while(map.size() > 2){
map.put(fruits[i],map.get(fruits[i])-1);
if(map.get(fruits[i]) <= 0){
map.remove(fruits[i]);
}
i ++;
}
}
return len;
}
}
三、力扣76. 最小覆盖子串
class Solution {
public String minWindow(String s, String t) {
Map<Character,Integer> map = new HashMap<>();
HashSet<Character> set = new HashSet<>();
int len = Integer.MAX_VALUE;
int count = 0;
String res = "";
for(int i = 0; i < t.length(); i ++){
set.add(t.charAt(i));
map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)+1);
}
for(int i = 0,j=0; j < s.length(); ){
while(count < set.size() && j < s.length()){
if(map.containsKey(s.charAt(j))){
map.put(s.charAt(j),map.get(s.charAt(j))-1);
if(map.get(s.charAt(j)) == 0){
count ++;
}
}
j ++;
}
while(count == set.size() && i < s.length()){
if(len > (j-i)){
len = j-i;
res = s.substring(i,j);
}
if(map.containsKey(s.charAt(i))){
if(map.get(s.charAt(i)) == 0){
count --;
}
map.put(s.charAt(i),map.get(s.charAt(i))+1);
}
i ++;
}
}
if(len != Integer.MAX_VALUE){
return res;
}
return res;
}
}