代码随想录 Day7

今日任务

454.四数相加Ⅱ
383.赎金信
15.三数之和
18.四数之和

454. 四数相加Ⅱ

考点：哈希表
链接：https://leetcode.cn/problems/4sum-ii/

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
        int count = 0;
        for(int i = 0; i < nums1.length; i++){
            for(int j = 0; j < nums2.length; j++){
                int sum = nums1[i] + nums2[j];
                if(record.containsKey(sum)){
                    record.put(sum, record.get(sum) + 1);
                }
                else{
                    record.put(sum, 1);
                }
            }
        }
        for(int i = 0; i < nums3.length; i++){
            for(int j = 0; j < nums4.length; j++){
                int sum = nums3[i] + nums4[j];
                int target = 0 - sum;
                if(record.get(target) != null){
                    count += record.get(target);
                }
            }
        }
        return count;
    }
}

383. 赎金信

考点：哈希表
链接：https://leetcode.cn/problems/ransom-note/

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

15. 三数之和

考点：双指针（哈希表麻烦）
链接：https://leetcode.cn/problems/3sum/
解题思路：卡哥视频
注意事项：此题还是有很多细节点的

1. 为什么这道题可以先对数组排序再求解？
   因为这道题需要我们返回的并不是数组元素的下标，而是数组中的元素，所以可以对数组进行排序，这样哪怕数组元素不在原来的位置也不会影响最终结果；
2. 为何这道题对 i 去重时要写成nums[i] == nums[i - 1]而不是nums[i] == nums[i + 1]？
   这和我们对 left 的处理有关，因为我们 left 的初始位置是在 i 右侧一个，如果直接判断 nums[i] 和 nums[i + 1] ，相当于我们会忽略掉nums[i] == nums[left]但其实结果符合nums[i] + nums[left] + nums[right] == 0的情况，所以去重时我们要使用nums[i] == nums[i - 1]这种判断方式；同理，后续对 left 和 right 的处理也是一样，left 向右移动，那么想要去重就要和 nums[left + 1] 比较，right 向左移动，想要去重就要和 nums[right - 1] 比较；
3. 我们需要先将结果加到 result 中，再对 left 和 right 去重，否则会导致result 中一个结果都没有。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                while(left < right && nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }
                while(left < right && nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }
                if(left < right && nums[i] + nums[left] + nums[right] == 0){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);
                    // while的时候务必注意下标范围
                    while(left < right && nums[left] == nums[left + 1]){
                        left++;
                    }
                    while(left < right && nums[right] == nums[right - 1]){
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

18. 四数之和

考点：
链接：https://leetcode.cn/problems/4sum/
思考问题：本题和454.四数相加Ⅱ的区别在哪里，为什么四数相加Ⅱ会简单很多？
四数相加Ⅱ是求四个数组之间的元素相加和为0的情况有多少种，哪怕元素值相等，但只要不是同一个数组中同位置的元素，就是不同的结果；但是此题要求元组不能重复；也就是说四数相加Ⅱ中(-1, -1, 1, 1)和(-1, 1, 1, -1)可能是两种结果，但在四数之和中，(-1, -1, 1, 1)和(-1, 1, 1, -1)只能算作一种结果，由去重产生的一系列需要考虑的情况导致了难度的上升。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        //错误的剪枝操作，nums[0]为负数且nums[0]>target是有可能的
        // if(nums.length < 4 || nums[0] > target){
        //     return result;
        // }
        for(int i = 0; i < nums.length - 3; i++){
            //这里的剪枝操作必须是 nums[i]>0 时才可以
            //因为在 nums[i]<0 时是有可能通过继续和负数相加得到target的
            if(nums[i] > 0 && nums[i] > target){
                return result;
            }
            //这里的if不要写成while，否则continue会死循环
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            for(int j = i + 1; j < nums.length - 2; j ++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while(left < right){
                    while(left < right && nums[i] + nums[j] + nums[left] + nums[right] > target){
                        right--;
                    }
                    while(left < right && nums[i] + nums[j] + nums[left] + nums[right] < target){
                        left++;
                    }
                    if(left < right && nums[i] + nums[j] + nums[left] + nums[right] == target){
                        result.add(Arrays.asList(nums[i], nums[j], 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 result;
    }
}

因为在三数之和时我没有进行剪枝操作，所以这道题写剪枝的时候就出现了很多意料之外的bug