import java.util.*;

public class Test {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new LinkedList<>();
        for (int i = 0; i < nums.length - 2;) {
            twoSum(nums,i,ans);
            int tmp = nums[i];
            while (i < nums.length && nums[i] == tmp) {
                i ++;
            }
        }
        return ans;
    }
    private void twoSum(int[] nums,int i,List<List<Integer>> ans) {
        int j = i + 1;
        int k = nums.length - 1;
        while (j < k) {
            if(nums[i] + nums[j] + nums[k] == 0) {
                // 找到了
                ans.add(Arrays.asList(nums[i],nums[j],nums[k]));

                int tmp = nums[j];
                while (j < k && nums[j] == tmp) {
                    j++; // 跳过重复的部分
                }
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j ++;
            } else {
                k --;
            }
        }
    }
    public int minSubArrayLen(int target, int[] nums) {
        // 和大于或等于k
        int l = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum >= target) {
                minLen = Math.min(minLen,l - r + 1);
                l ++;
            }
        }
        return minLen == Integer.MAX_VALUE ? -1 : minLen;
    }
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        long product = 1;
        int l = 0;
        int ans = 0;
        for (int r = 0; r < nums.length; r++) {
            product*=nums[r];
            while (product >= k && l <= r) {
                product /= nums[l++];
            }
            ans += r >= l ? r - l + 1 : 0;
        }
        return ans;
    }
    public int subarraySum(int[] nums, int k) {
        // 设preSum[i] 为前i个数的和
        // 假设我们当前遍历到了第i个数
        // 如果存在某个j，j<i 并且 preSum[j] = preSum[i] - k
        // 那么这个时候 从j到i的子数组就是一个满足条件的子数组（因为preSum[i] - preSum[j] == k，并且i->j的和为preSum[i]-preSum[j]）
        // 所以对于每个i只需要找到有多少个这样的j就可以了
//        int n = nums.length;
//        int[] preSum = new int[n+1];
//        for (int i = 0; i < n; i++) {
//            preSum[i+1] = preSum[i] + nums[i];
//        }
//        int ans = 0;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 0; j < i; j++) {
//                if(preSum[j] == preSum[i] - k) {
//                    ans ++;
//                }
//            }
//        }
//        return ans;
        // 优化
        // 重点在于找到有多少个这样的j
        // 用一个哈希表来存放已经遍历过的元素里前缀和的情况
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1); // 和为0的有一种，就是前0个元素
        int ans = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            ans += map.getOrDefault(sum - k,0);
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ans;
    }
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int sum = 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i] == 0 ? -1 : 1;
            if(map.containsKey(sum)) {
                ans = Math.max(ans,i - map.get(sum));
            } else {
                map.put(sum,i);
            }
        }
        return ans == Integer.MIN_VALUE ? 0 : ans;
    }
    public boolean checkInclusion(String s1, String s2) {
        if(s2.length() < s1.length()) return false;
        int[] mask = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            mask[s1.charAt(i) - 'a']++;
            mask[s2.charAt(i) - 'a']--;
        }
        if(allZero(mask)) {
            return true;
        }
        for (int i = s1.length(); i < s2.length(); i++) {
            mask[s2.charAt(i) - 'a']--;
            mask[s2.charAt(i-s1.length()) - 'a']++;
            if(allZero(mask)) {
                return true;
            }
        }
        return false;
    }
    private boolean allZero(int[] mask) {
        for (int num: mask) {
            if(num != 0) return false;
        }
        return true;
    }
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new LinkedList<>();
        if(s.length() < p.length()) {
            return ans;
        }
        int i = 0;
        int j = 0;
        int[] map = new int[26];
        for (;i < p.length();) {
            map[p.charAt(i) - 'a']++;
            map[s.charAt(i) - 'a']--;
            i++;
        }
        if(allZero(map)) {
            ans.add(0);
        }
        for (;i < s.length();i++,j++) {
            map[s.charAt(i) - 'a']--;
            map[s.charAt(j) - 'a']++;
            if(allZero(map)) {
                ans.add(j+1);
            }
        }
        return ans;
    }
    public int lengthOfLongestSubstring(String s) {
        // 没有重复字符
        // 也就是不存在大于1的字符
        int[] map = new int[256];
        int j = 0;
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i)]++;
            while (hasGreaterThanOne(map)) {
                map[s.charAt(j)]--;
                j++;
            }
            ans = Math.max(ans,i - j + 1);
        }
        return ans;
    }
    private boolean hasGreaterThanOne(int[] map) {
        for (int num: map) {
            if(num > 1) return true;
        }
        return false;
    }
    public String minWindow(String s, String t) {
        if(s.length() < t.length()) {
            return "";
        }
        int[] map = new int[256];
        for (int i = 0; i < t.length(); i++) {
            map[s.charAt(i)]--;
            map[t.charAt(i)]++;
        }

        int j = 0;
        int minLen = -1;
        int minPos = 0;
        if(check(map,t)) {
            minPos = 0;
            minLen = t.length();
        }
        for (int i = t.length(); i < s.length(); i++) {
            map[s.charAt(i)]++;
            while (check(map,t)) {
//                String tmp = s.substring(j,i+1);
//                if(tmp.length() < ans.length()) {
//                    ans = tmp;
//                }
                if(minLen > i - j + 1) {
                    minLen = i - j + 1;
                    minPos = j;
                }
                map[s.charAt(j)]++;
                j++;
            }
        }
        return s.substring(minPos,minPos + minLen);
    }
    private boolean check(int[] mask,String t) {
        for (int i = 0; i < t.length(); i++) {
            if(mask[t.charAt(i)] > 0) {
                return false;
            }
        }
        return true;
    }
    
}