5 滑动窗口

public static int subarraySum(int[] nums, int k) {
    int l = 0, r = 0;
    while(r < nums.length){
        // 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 < s2.length()) {
            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 < s.length()){
            char ch = s.charAt(r);
            // 1. r向右移动
            // 需要ch
            if(cnt[ch] > 0){
                count --;
            }
            cnt[ch] --;
            // 2. 满足条件，l右移动
            if(count == 0){
                while(l < r && cnt[s.charAt(l)] < 0){
                    cnt[s.charAt(l)]++;
                    l++;
                }
                if(r - l + 1 < size){
                    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<Integer> findSubstring(String s, String[] words) {
        List<Integer> 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<String, Integer> map = new HashMap<String, Integer>();
        for(String word : words){
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // System.out.print("map: " + map);
        for(int i = 0; i < s.length() - len + 1; i++){
            String sub = s.substring(i, i + len);
            HashMap<String, Integer> tmp_map = new HashMap<>();
            for(int j = 0; j < len; j+=one_word){
                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<Character, Integer> map = new HashMap<Character, Integer>();
        for(int i = 0; i < s.length(); 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 < nums.length){
            // 1. r 向右移动
            cur_sum += nums[r];
            // 2.满足条件了，l向右移动
            while(l < r && cur_sum - nums[l] >= target){
                cur_sum -= nums[l];
                l++;
            }
            // l 还是需要想右走一步，然后重复吧
            if(cur_sum >= target){
                if(r - l + 1 < res){
                    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<Integer> deque = new LinkedList<>();
        int[] res = new int[len - k + 1];
        for(int i = 0; i < k; i++){
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }


        res[0] = deque.peekFirst();


        for(int i = k; i < len; i++){
            if(deque.peekFirst() == nums[i-k]){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && deque.peekLast() < nums[i]){
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }
}