leetcode-06-[454]四数相加II[383]赎金信 [15] 三数之和 [18] 四数之和

重点：

三数之和、四数之和 适合用双指针

哈希表需要考虑的边界条件太多

一、[454]四数相加II

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

二、[383]赎金信

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length()>magazine.length()) {
            return false;
        }
        int[] res=new int[26];
        for(int i=0;i<magazine.length();i++){
            res[magazine.charAt(i)-'a']++;
        }
        for(int j=0;j<ransomNote.length();j++){
            res[ransomNote.charAt(j)-'a']--;
        }
        for(int k:res){
            if(k<0){
                return false;
            }
        }
        return true;
    }
}

三、[15] 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //双指针
        //升序
        Arrays.sort(nums);
        //注意一下
        List<List<Integer>> res = new ArrayList<>();
        int left,right;
        for(int i=0;i< nums.length;i++){
            left = i + 1;
            right = nums.length - 1;
            //剪枝
            if (nums[i] > 0) {
                return res;
            }
            //i去重
            if (i >= 1 && nums[i] == nums[i - 1]) {
                continue;
            }
            while (left < right) {
                int sum=nums[i] + nums[left] + nums[right];
                if(sum<0){
                    left++;
                } else if (sum>0) {
                    right--;
                }else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //去重,在找到三元组之后！！！！！
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

四、[18] 四数之和 

重点：

a+b+c+d=target，先排序

1、剪枝时，需要考虑负数的情况（与三数之和略有不同）

如[-5,-4,0,1,2]  -6  

其中 -5>-6  

但-5+(-4)+1+2=--6  存在四元组

只需要排序后的数组，在a>0时，再进行比较a>target即可,满足则剪枝

2、去重

b去重时，考虑[2,2,2,2,2]这种情况

应该注意b 、a 可以相同，故 j > i+1（每次开始时 j = i+1）

c、d 去重时，应在找到四元组之后，注意 if 与 while 的使用

3、int会溢出

nums[k] + nums[i] + nums[left] + nums[right] > target  int会溢出

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int i=0;i< nums.length;i++){
            //剪枝 考虑负数的情况  [-5,-4,0,1,4]  -6  -5>-6   -5+(-4)=-9仍然存在
            if(nums[i]>0&&nums[i]>target){
                return res;
            }
            //去重
            if(i>=1&&nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j< nums.length;j++){
                int left=j+1;
                int right= nums.length-1;
                //去重  注意j>i+1  j与i值可以相同[2,2,2,2,2]
                if(j>i+1&&nums[j]==nums[j-1]){
                    continue;
                }
                while(left<right){
                    // 注意 int 会溢出
                    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum<target){
                        left++;
                    } else if (sum>target) {
                        right--;
                    }else {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        res.add(list);
                        //left去重
                        while (left<right&&nums[left]==nums[left+1]){
                            left++;
                        }
                        //right去重
                        while(left<right&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }
}