5滑动窗口

public static int subarraySum(int[] nums, int k) {
int l = 0, r = 0;
while(r // 1. r 向右移动
// 2.满足条件了，l向右移动
while(满足或者超过预期){
l++;
}
if(刚好满足){
// 加入结果集res
l++;
}
r++;
}
return res;
}

class Solution {
public boolean checkInclusion(String s1, String s2) {
int n = s1.length(), m = s2.length();
if(n > m) return false;
int[] cnt = new int[128];
for (char ch : s1.toCharArray()) {
cnt[ch]++;
}
int l = 0, r = 0;
// 1. r向右滑动
while(r int ch = s2.charAt(r);
cnt[ch]--;
// 2. 该窗口不符合了， l向右滑动
while(cnt[ch] <0){
cnt[s2.charAt(l)]++;
l++;
}
// 3. 如果该窗口刚好符合题意，加入结果集合
if(r - l + 1 == n){
return true;
}
r++;
}
return false;
}
}

class Solution {
public String minWindow(String s, String t) {
if(s == null || s.length() == 0 || t == null || t.length() == 0) return "";
int[] cnt = new int[128];
int l = 0, r = 0, count = t.length();
int start = 0, size = Integer.MAX_VALUE;
for(char c : t.toCharArray()){
cnt[c] ++;
}
while(r char ch = s.charAt(r);
// 1. r向右移动
// 需要ch
if(cnt[ch] > 0){
count --;
}
cnt[ch] --;
// 2. 满足条件，l右移动
if(count == 0){
while(l cnt[s.charAt(l)]++;
l++;
}
if(r - l + 1 size = r - l + 1;
start = l;
}
cnt[s.charAt(l)] ++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
}

class Solution {
public List findSubstring(String s, String[] words) {
List res = new ArrayList<>();
if(s == null || s.length() == 0 || words == null || words.length == 0) return res;
int one_word = words[0].length();
int len = one_word * words.length;
Map map = new HashMap();
for(String word : words){
map.put(word, map.getOrDefault(word, 0) + 1);
}
// System.out.print("map: " + map);
for(int i = 0; i String sub = s.substring(i, i + len);
HashMap tmp_map = new HashMap<>();
for(int j = 0; j String w = sub.substring(j, j + one_word);
tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
}
// System.out.print("tmp_map: " + tmp_map);
if(map.equals(tmp_map)) res.add(i);
}
return res;
}
}

class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, max = 0;
Map map = new HashMap();
for(int i = 0; i char ch = s.charAt(i);
if(map.containsKey(ch))
left = Math.max(left, map.get(ch) + 1);
max = Math.max(max, i - left + 1);
map.put(ch, i);
}
return max;
}
}

class Solution {
public int minSubArrayLen(int target, int[] nums) {
int res = Integer.MAX_VALUE;
int l = 0, r = 0, cur_sum = 0;
while(r // 1. r 向右移动
cur_sum += nums[r];
// 2.满足条件了，l向右移动
while(l = target){
cur_sum -= nums[l];
l++;
}
// l 还是需要想右走一步，然后重复吧
if(cur_sum >= target){
if(r - l + 1 res = r - l + 1;
}
cur_sum -= nums[l];
l++;
}
r++;
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if(len == 0 || k == 0) return new int[0];
Deque deque = new LinkedList<>();
int[] res = new int[len - k + 1];
for(int i = 0; i while(!deque.isEmpty() && deque.peekLast() deque.removeLast();
}
deque.addLast(nums[i]);
}
res[0] = deque.peekFirst();
for(int i = k; i if(deque.peekFirst() == nums[i-k]){
deque.removeFirst();
}
while(!deque.isEmpty() && deque.peekLast() deque.removeLast();
}
deque.addLast(nums[i]);
res[i - k + 1] = deque.peekFirst();
}
return res;
}
}