当前位置：首页 > article >正文

代码随想录算法训练营第 7 天（哈希表2）| 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

article 2025/1/15 7:31:17

一、454.四数相加II

题目：https://leetcode.cn/problems/4sum-ii/

视频：https://www.bilibili.com/video/BV1Md4y1Q7Yh

讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

不需要去重，因为取自的数可能不是同一个，HashMap不能去重 (HashSet可以去重)

| 数组，set，map选型：

因为字母异位词那道题，元素数量是有限的，所以用数组

但是这道题元素数量很多，所以用set或者map

但是这道题不仅要考虑是否出现过，还要看出现的次数，所以用Map（HashMap）

| 思路：

此题key是求的和，value是这个和在Map中出现的次数

| 好用的方法：map.getOrDefault() java.util.Map接口

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res=0;   //要初始化，写一个初始值
        Map<Integer, Integer> map = new HashMap<Integer,Integer>();

        for(int i: nums1){
            for(int j: nums2){
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum,0)+1);   //1
            }
        }

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

map.getOrDefault(i, j)：在Map中找key是i的元素，找到返回value,找不到返回j。
Java中的Map.getOrDefault()方法详解

二、383. 赎金信

题目：https://leetcode.cn/problems/ransom-note/

视频：

讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

开始想到用Map实现，其实在本题的情况下，使用map的空间消耗要比数组大一些的，因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！数据量大的话就能体现出来差别了。 所以此题用数!组!更加简单直接有效！

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'] ++;
        }

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

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

| toCharArray()是一个字符串（String）类的方法，它的作用是将字符串转换成一个字符数组（char[]）。

例如，假设有一个字符串magazine的值为"hello"，那么执行magazine.toCharArray()后，会得到一个字符数组，其内容为{‘h’, ‘e’, ‘l’, ‘l’, ‘o’}。这样就可以通过遍历这个字符数组，对字符串中的每个字符进行单独的操作，比如在上述代码片段中，通过遍历magazine字符串转换成的字符数组，来统计每个字符出现的次数。

尝试过程：

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'] ++;
        }

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

        for(int i : record){
            if(record[i] < 0) return false;  //这里有问题
        }
        return true;
    }
}

i是循环中的指针，不是数组的下标！！比较的是他所指向的数组，所以不用record[i]，应该是i

| 一个求长度的易错点：

数组求长度：nums.length;

字符串求长度：str.length();

三、15. 三数之和

题目：https://leetcode.cn/problems/3sum/

视频：https://www.bilibili.com/video/BV1GW4y127qo

讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

| 此题使用双指针法更方便

使用双指针的时候要注意，数组要是有序的状态

| 进一步思考：

1、如果第一位（每次循环i所指的数）是大于零的，那就不用看了，因为是有序的序列，后面数更大，三数之和肯定不能为零。

2、如果i所指向的数，和上一轮所指向的数一样，也不用看了，因为结果和上一轮循环的结果一样，而返回的结果要去重。

3、Arrays.asList()，把数组变成集合

4、预先查看下一轮循环的right和left，和此轮是不是一样，一样的话就不用比了，继续下一位

| ★★★几次判断/查重：

1、循环进来先判断第一位

2、之后的循环，首先看这次循环跟上次循环是否一样，一样就跳过此次循环

3、预看下一轮的left和right所指是否和次轮一样，一样就不用比了，再跳一个，接着找下一个与i对应的left,right对儿

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {

        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for(int i = 0; i < nums.length; i++){
            if(nums[i]>0) return result;     //1

            if(i>0 && nums[i] == nums[i-1]) continue;  //2 避免重复查找

            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                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])); //3
					//4
                    while(left < right && nums[left] == nums[left+1]) left++;
                    while(left < right && nums[right] == nums[right-1]) right--;

                    left++;
                    right--;
                }
            }
        }

        return result;
    }
}

| “Arrays.sort(nums); 该方法的作用是对数组nums进行排序。

Arrays是Java的一个工具类，提供了各种静态方法用于操作数组，如排序、搜索、比较等。
sort是Arrays类的一个静态方法，用于对数组进行排序。

| continue; ：如果当前元素与前一个元素相同，则跳过当前循环，直接进入下一次循环。这样做的目的是避免重复计算相同的三元组。

| asList() : 此方法通常用于将数组转换为列表。例如在Java中，Arrays.asList()方法可以将一个数组包装成一个固定大小的列表，这样就可以使用列表的一些方法来操作这个数组了。

四、18. 四数之和

题目：https://leetcode.cn/problems/4sum/

视频：https://www.bilibili.com/video/BV1DS4y147US

讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

| 剪枝操作：剪枝：属于算法优化，即通过某种判断，避免不必要的搜索遍历

| 审题：454.四数相加是4个数相加等于0， 18.四数之和是4个数相加等于target，两个题因为相加结果不同，两题解题思路不同

| 基本思路：

此题基本思路和三数之和一样，只不过是多了一层循环。不过要多注意一些细节

| 进一步思考：

两个数相加不一定越来越大，比如负数，如果i=-4, j=-1, target= -5

如果一开始就判定i>target的话，此次循环就落下了！

| 对于if (nums[i] > target && nums[i] >= 0) break;这里剪枝的部分是正数部分，那负数部分能不能有相关的剪枝呢？

对于负数部分的剪枝，主要考虑的是当当前数加上之前已经固定的数的和已经小于目标值，并且当前数为负数时，由于数组已排序，后续的数会更小，因此可以提前结束循环。以下是相关的剪枝代码：

if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] < target && nums[i] < 0) break;

这条剪枝语句的含义是，如果当前固定的两个数 nums[i] 和 nums[j] 加上数组中接下来最小的两个数 nums[j + 1] 和 nums[j + 2] 的和仍然小于目标值，并且 nums[i] 是负数，那么由于数组已经排序，后续的数只会更小，因此可以提前结束外层循环。

同理，对于内层循环，也可以添加类似的剪枝条件。

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

        for(int i=0; i < nums.length; i++){
            //i的两次剪枝
            if(nums[i] > target && nums[i]>=0) break;
            if(i>0 && nums[i] == nums[i-1]) continue;

            for(int j=i+1; j < nums.length; j++){
                //j的两次剪枝
                if(nums[i] + nums[j] > target && nums[i]+nums[j]>=0) break;
                if(nums[j] == nums[j-1] && j>i+1) continue;

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