Top 150 · 滑动窗口（4 题）

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minL =Integer.MAX_VALUE;
        int l =0;
        int r = 0;
        int cur = 0;
        int n = nums.length;

        while(r<n){
            if(cur< target){//r++
                cur+=nums[r];
                r++;
            }else{//l++
                minL = Math.min(minL,r-l);
                cur -= nums[l];
                l++;
            }
        }

        while(l<n){
            if(cur >= target){
                minL = Math.min(minL,r-l);
                cur -= nums[l];
                l++;
            }else{
                break;
            }
        }
        return minL==Integer.MAX_VALUE ? 0:minL;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map = new HashMap<>();
        int ans =0;
        int l=0;
        int r =0;
        int n = s.length();

        while(r < n){
            if(map.containsKey(s.charAt(r))){
                int oldPos = map.get(s.charAt(r));

                while(l<=oldPos){
                    map.remove(s.charAt(l));
                    l++;
                }

                map.put(s.charAt(r),r);
                r++;
            }else{
                map.put(s.charAt(r),r);
                ans = Math.max(ans,r-l+1);
                r++;
            }
        }


        return ans;
    }
}

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        HashMap<String,Integer> map = new HashMap<>();
        HashMap<String,Integer> window = new HashMap<>();

        int patternLen = words[0].length();
        int n = words.length;
        int sn = s.length();


        for (int i = 0; i < n; i++) {
            map.put(words[i],map.getOrDefault(words[i],0)+1);
        }
        List<Integer> ans = new ArrayList<>();

        for (int i = 0; i < patternLen; i++) {
            int l = i;
            int r = i;
            int count = 0;
            while (r + patternLen <= sn) {

                String word = s.substring(r, r + patternLen);
                r += patternLen;

                // ① word 不在 map
                // window 清空
                // count = 0
                // l = r
                if(!map.containsKey(word)){
                    window.clear();
                    count = 0;
                    l=r;
                }
                // ② word 在 map
                // 加入 window
                // count++
                else{
                    window.put(word,window.getOrDefault(word,0)+1);
                    count++;
                    // ③ 如果 word 超量
                    // while (window[word] > map[word])
                    // 从 l 移出一个 word
                    while(window.get(word) > map.get(word)){
                        String delete = s.substring(l,l+patternLen);
                        if(window.get(delete) == 1){
                            window.remove(delete);
                        }else{
                            window.put(delete,window.get(delete) - 1);
                        }
                        l+= patternLen;
                        count--;
                    }
                    // ④ count == n
                    // ans.add(l)
                    if(count == n){
                        ans.add(l);
                    }
                }
            }

            window.clear();
        }
        return ans;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        if(m < n) return "";

        int l = 0;
        int r = 0;

        int minL =0;
        int minR =10000000;

        HashMap<Character,Integer> mapT = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            mapT.put(t.charAt(i),mapT.getOrDefault(t.charAt(i),0)+1);
        }

        HashMap<Character,Integer> window = new HashMap<>();

        int valid =0;
        while(r< m){
            char c = s.charAt(r);
            r++;

            window.put(c, window.getOrDefault(c,0)+1);
            if(mapT.getOrDefault(c,-1).equals(window.get(c)))valid++;
            while(valid == mapT.size()){
                if(r-l < minR-minL){
                    minL = l;
                    minR = r;
                }
                char delete = s.charAt(l);
                if(window.get(delete).equals(mapT.getOrDefault(delete,-1)))valid--;
                window.put(delete,window.get(delete) -1);
                l++;
            }
        }
        if(minR == 10000000)return "";
        return s.substring(minL,minR);
    }
}