class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map = new HashMap<>();
        int tmp;
        int ret = 0;
        for(int i:nums1){
            for(int j:nums2){
                tmp = i+j;
                if(map.containsKey(tmp)){
                    map.put(tmp,map.get(tmp)+1);
                }else{
                    map.put(tmp,1);
                }
            }
        }
        for(int i:nums3){
            for(int j:nums4){
                tmp = i+j;
                if(map.containsKey(0-tmp)){
                    ret += map.get(0-tmp);
                }
            }
        }
        return ret;
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] arr = new int[26];
        for(char c : magazine.toCharArray()){
            arr[c-'a'] +=1;
        }

        for(char c:ransomNote.toCharArray()){
            arr[c-'a'] -=1;
        }

        for(int i:arr){
            if(i<0){
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){
            if(nums[i] > 0){
                return ret;
            }
            if(i>0 && nums[i] == nums[i-1]){
                continue;
            }

            int left = i+1;
            int right = nums.length-1;
            while(right>left){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    right--;
                }else if(sum<0){
                    left++;
                }else{
                    ret.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(right>left && nums[right] == nums[right-1]){
                        right--;
                    }
                    while(right > left && nums[left] == nums[left+1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return ret;
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);

        for(int i = 0;i < nums.length;i++){
            if(nums[i]>0 && nums[i]>target){
                return ret;
            }
            if(i>0 && nums[i-1] == nums[i]){
                continue;
            }
            for(int j = i+1;j<nums.length;j++){
                if(j > i+1 && nums[j-1] == nums[j]){
                    continue;
                }
                int left = j+1;
                int right = nums.length-1;
                while(left<right){
                    long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum > target){
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left < right && nums[right] == nums[right-1]){
                            right--;
                        }
                        while(left < right && nums[left] == nums[left+1]){
                            left++;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return ret;
    }
}