class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int len = Integer.MAX_VALUE;//剛開(kāi)始定義長(zhǎng)度是int可以表示最大整數(shù)
        int n = nums.length;
        for(int left = 0,right = 0; right < n;right++){
            sum += nums[right];//入窗口
            //結(jié)果判斷
            while(sum >= target){
                len = Math.min(len , right - left + 1);//結(jié)果更新
                sum -= nums[left++]; //出窗口
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String ss) {
        int[] hash = new int[128];//這里使用數(shù)組來(lái)表示其hash，如果其對(duì)應(yīng)的位置>1說(shuō)明有重復(fù)的
        int len = 0;
        char[] s = ss.toCharArray();//將其字符串轉(zhuǎn)換成字符數(shù)組，方便后面使用
        //使用同向雙指針，滑動(dòng)窗口
        for(int left = 0,right = 0;right < s.length;right++){
            //入窗口
            hash[s[right]]++;//字符對(duì)應(yīng)的ASCLL碼值作為下標(biāo)++
            //判斷，如果>1，說(shuō)明有重復(fù)的了，就要出窗口
            while(hash[s[right]] > 1){
                //出窗口
                hash[s[left++]]--;
            }
            //更新結(jié)果
            len = Math.max(len,right - left+1);
        }
        return len;
    }
}

class Solution {
    public int longestOnes(int[] nums, int k) {
        int len = 0;
        int n = nums.length;
        int count = 0;//用于統(tǒng)計(jì)當(dāng)前區(qū)間0的個(gè)數(shù)
        for(int left = 0,right = 0;right < n;right++){
            //記錄當(dāng)前0的個(gè)數(shù)
            if(nums[right] == 0){
                count++;
            }
            //出窗口
            while(count > k){
                if(nums[left++] == 0){
                    count--;
                }
            }
            //更新結(jié)果
            len = Math.max(len , right - left + 1);
        }
        return len;
    }
}

class Solution {
    public int minOperations(int[] nums, int x) {
        //這里采用正難則反的思想，我們是每次從最右邊和最左邊找數(shù)相加，看何時(shí)等于x
        //我們可以轉(zhuǎn)換為在這個(gè)數(shù)組連續(xù)區(qū)間找一個(gè)最長(zhǎng)的長(zhǎng)度和為 整個(gè)數(shù)組的和 - x
        int sum = 0;//nums整個(gè)數(shù)組的和
        int n = nums.length;
        for(int i = 0; i < n;i++){
            sum += nums[i];
        }
        //此時(shí)我們的目標(biāo)值變成sum - x
        int target = sum - x;
        //如果全部sum和都<x說(shuō)明找不到
        if(target < 0){
            return -1;
        }
        int total = 0;
        int len = -1;
        //后面就使用滑動(dòng)窗口來(lái)找最長(zhǎng)子串使其長(zhǎng)度等于target目標(biāo)值
        for(int left = 0,right = 0;right < n;right++){
            //入窗口
            total += nums[right];
            //判斷
            while(total > target){
                total -= nums[left++];//出窗口
            }
            //等于的時(shí)候才更新結(jié)果
            if(total == target){
               len =  Math.max(len,right - left + 1);
            }
        }
        return len == -1 ? -1 : n - len;
    }
}

class Solution {
    public int totalFruit(int[] fruits) {
        //此時(shí)我們使用一個(gè)數(shù)組來(lái)實(shí)現(xiàn)hash
        int n = fruits.length;
        int[] hash = new int[n+1];
        int len = 0;//最長(zhǎng)的長(zhǎng)度
        for(int left = 0,right = 0,kinds = 0;right < n ;right++){
            //入窗口
            if(hash[fruits[right]] == 0){
                kinds++;//如果這個(gè)窗口沒(méi)有添加過(guò)這個(gè)元素，此時(shí)種類增多
            }
            hash[fruits[right]]++;
            //當(dāng)kinds>2進(jìn)行出窗口
            while(kinds > 2){
                //出窗口
                hash[fruits[left]]--;
                //此時(shí)如果這個(gè)連續(xù)的區(qū)間沒(méi)有了這個(gè)元素，此時(shí)的種類就減小
                if(hash[fruits[left]] ==0){
                    kinds--;
                }
                left++;
            }
            //更新結(jié)果
            len = Math.max(len,right - left + 1);
        }
        return len;
    }
}

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        //使用兩個(gè)數(shù)組來(lái)模擬hash
        int[] hash1 = new int[26];//用來(lái)放pp字符串的所有字符信息
        for(char ch : p){
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];//此時(shí)的用來(lái)放窗口中每個(gè)字符出現(xiàn)的次數(shù)
        int n = pp.length();
        //此時(shí)的count是用來(lái)統(tǒng)計(jì)有效字符個(gè)數(shù)
        for(int left = 0,right = 0,count = 0;right<ss.length();right++){
            char in = s[right];
            if(++hash2[in - 'a'] <= hash1[in - 'a']){//入窗口
                count++;
            }
            //判斷
            if(right - left + 1 > n){
                //出窗口
                char out = s[left++];
                if(hash2[out - 'a']-- <= hash1[out - 'a']){
                    count--;
                }
            }
            //更新結(jié)果
            if(count == n){
                ret.add(left);
            }
        }
        return ret;
    }
}

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

        //使用map來(lái)存放words
        Map<String,Integer> hash1 = new HashMap<>();
        for(String word : words){
            hash1.put(word,hash1.getOrDefault(word,0)+1);
        }
        int n = words[0].length();//單詞長(zhǎng)度

        int m = words.length;//有多少單詞
        //此時(shí)要循環(huán)n次滑動(dòng)窗口，因?yàn)槲覀儗⒚總€(gè)單詞這些字符看成了一個(gè)整體放入hash
        for(int i = 0;i < n;i++){
            //使用count來(lái)統(tǒng)計(jì)有效單詞個(gè)數(shù)
            Map<String,Integer> hash2 = new HashMap<>();
            for(int left = i,right = i,count = 0;right <= s.length() - n;right += n){
                String in = s.substring(right,right+n);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)){
                    count++;
                }

                //出窗口
                if(right - left + 1 > m*n){
                    String out = s.substring(left,left+n);
                    if(hash2.get(out) <= hash1.getOrDefault(out,0)){
                        count--;
                    }
                    hash2.put(out,hash2.get(out) - 1);
                    if(hash2.get(out) == 0){
                        hash2.remove(out);
                    }
                    left += n;
                }
                if(count == m){
                    ret.add(left);
                }
            }
        }
        return ret;
    }
}

class Solution {
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        //使用數(shù)組來(lái)模擬hash
        int[] hash1 = new int[128];
        int kinds = 0;//記錄tt中出現(xiàn)字符的種類
        for (char ch : t) {
            if (hash1[ch]++ == 0) {
                kinds++;
            }
        }

        int minlen = Integer.MAX_VALUE;
        int begin = -1;//記錄其起始位置和長(zhǎng)度即可
        int[] hash2 = new int[128];//記錄窗口中字符
        for (int left = 0, right = 0, count = 0; right < ss.length(); right++) {
            char in = s[right];
            //當(dāng)這個(gè)字符的數(shù)量和hash1相同時(shí)候，count++
            if (++hash2[in] == hash1[in]) {
                count++;
            }
            while (kinds == count) {
                //更新結(jié)果
                if (right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) {
                    count--;
                }
            }
        }
        return begin == -1 ? new String() : ss.substring(begin, begin + minlen);
    }
}