代码随想录算法训练营| 454.四数相加II 、 383. 赎金信 、 15. 三数之和 、 18. 四数之和

 454.四数相加II

题目

参考文章

思路：设置一个map，用于存储nums1和nums2中相加的和的值以及出现的次数，因为由题目可以知道a+b+c+d=0，即a+b=0-(c+d)，所以遍历nums3和nums4时，看看其中元素的和是否在map中出现过（即0-c-d是否出现过），如果出现过，则用一个变量res存储map中对应的value（假设因为nums1和nums2中的和有2个相同的，与nums3和nums4中的某个和相加为零，故有2个元组匹配了）

代码：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res=0;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        //统计num1 num2数组的和，以及次数
        for(int i:nums1){
            for(int j:nums2){
                int sum=i+j;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }

        for(int i:nums3){
            for(int j:nums4){
                res+=map.getOrDefault(0-i-j,0);
            }
        }

        return res;
    }
}

383. 赎金信

题目

参考文章

思路：由题目意思可以知道，magazine中的元素可以组成ransomNote中的元素，而且magazine中的字符每个只能使用一次，也都是小写字母。所以这题如果当ransomNote的长度大于magazine时，直接返回false即可。然后定义一个record数组用于记录字符出现的次数，先遍历magazine字符串中的字符每次+1，然后遍历ransomNote中的字符每次-1。最后遍历这个record数组，如果其中某个数值小于零，则表示ransoomNote有个别元素不由magazine中的元素组成，返回false，最后如果都正常则返回true

代码：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if(ransomNote.length()>magazine.length()){
            return false;
        }

        int[] record=new int[26];

        for(char c:magazine.toCharArray()){
            record[c-'a']+=1;
        }

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

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

        return true;
    }
}

15. 三数之和

题目

参考文章

思路：本题运用二维数组+双指针的做法。因为题目是找一个数组中三个数的和，而且同一个位置的数不能重复出现（就是题目中的i，j，k三个位置），但是不同位置的数值可以重复。

首先，把二维数组排序，为了后面方便运用双指针。排序后，遍历数组，如果nums[i]>0了，就直接返回result即可，因为数组已经排序，后面的值已经没有意义了；如果当前num[i]的值和nums[i-1]相等，表示当前值和之前获取到的nums[i]值重复了，不符合题目要求，所以直接过滤掉这一次的循环。如上两次步骤做好后，就是定义left和right双指针了，用于三个数相加；用while循环，前提是right一定得大于left，但不能等于，等于的时候，right和left的值就重复了，不符合题意了；定义一个sum，存储三个值的和，当sum>0时，表示值过大，把right--，减小数值继续循环，当sum<0时，表示数值过小，把left++，增大数值继续循环；当sum==0时，就把对应的这三个值存储到二维数组result中，然后缩小双指针的范围即left++，right-- （前提是left和right已经去重的情况下，之后会写道）；到了这里就是最重要的一步，前面已经把nums[i]的值去重了，这里就要把nums[left],nums[right]的值也要去重，因为left是前进的，right是后退的，所以当nums[right]==nums[right-1]时，right--，过滤掉下一个要加的nums[right]值，同理left则是 当nums[left]==nums[left+1]时，left++。 

代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        //找a+b+c的和
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                return result;
            }

            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{
                    result.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 result;
    }
}

18. 四数之和 

题目

参考文章

思路：此题的思路和15题的三数之和思路差不多，只是i循环外再嵌套了一层k循环，多加了个参数target，所以再加一个剪枝操作即可（其实15题也用了剪枝操作，只是少了target的比较）。这个剪枝操作出来判断当前值是否大于零外，还要判断这个值是否大于target，如果不大于target也是不用剪枝的；去重原理与15题一致。然后到 i 层循环，这个时候，因为 i 层循环外已经嵌套了k层循环，所以i的值要从i=k+1开始，而剪枝操作要以 nums[k]+nums[i]为依据；然后去重发生了些许变化，因为 i 从k+1开始，所以要当i>k+1时 判断去重，后面的双指针就完全和15题一样了，就不多赘述了哈

代码：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> result = new ArrayList<>();  // 结果集
        for(int k=0;k<nums.length;k++){
            //剪枝操作
            if(nums[k]>target&& nums[k]>=0){ //表示已经不符合题目要求了，直接退出循环，前提是nums[k]>0
                break;
            }
            //去重操作
            if(k>0&&nums[k]==nums[k-1]){
                continue;
            }

            for(int i=k+1;i<nums.length;i++){
                //剪枝操作
                if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0){ //因为这里是从k上继承下来的，所以要加上k下表下的值进行剪枝
                    break;
                }
                if(i>k+1&&nums[i]==nums[i-1]){
                    continue;
                }

                int left=i+1;
                int right=nums.length-1;
                while(right>left){
                    long sum=(long) nums[k]+nums[i]+nums[left]+nums[right];
                    if(sum>target){
                        right--;
                    }else if(sum<target){
                        left++;
                    }else{
                         result.add(Arrays.asList(nums[k], 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 result;
    
        
     }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}