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