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

时间：2025-03-24 11:02:01

目录

454.四数相加Ⅱ

1.解题思路

2.我的实现

实现遇到的问题

怎么计数：

代码

3.标准实现

区别

4.题目总结

383.赎金信

1.解题思路

2.我的实现

3.标准实现

区别

4.题目总结

15.三数之和（！！！）

1.解题思路

2.我的实现

实现遇到的问题

怎么去重：

代码

3.标准实现

4.题目总结

1. 双指针法：

2. 去重策略：

18.四数之和（！！！）

1.解题思路

2.我的实现

实现遇到的问题

代码

3.标准实现

4.题目总结

1. 排序的必要性

2. 双指针法的应用

3. 去重处理

4. 边界条件

5. 整数溢出问题

6. 复杂度分析

7. 扩展思考

454.四数相加Ⅱ

题目链接：四数相加Ⅱ

1.解题思路

把数组A+B的和遍历后放进一个数组中，再判断C+D中有没有我们想要的

这个是不怕重复的

这个题如果用数组下标来做映射的话就不行，因为值可能很大，所以只能考虑set或者map

为了统计sum和次数，所以需要两个值，就用map

map中key值存A+B的和，value存次数，再判断0-（C+D）是否存在在map中，出现了一次就加value里面存的值

2.我的实现

实现遇到的问题

怎么计数：

使用

getOrDefault(sum, 0)

解释

V getOrDefault(Object key, V defaultValue)

  • key：要查找的键。
  • defaultValue：如果 Map 中不存在该键，则返回的默认值。

当你调用 getOrDefault(sum, 0) 时，Map 会尝试根据键 sum 查找对应的值。

  • 如果 sum 存在于 Map 中，则返回与 sum 关联的值。
  • 如果 sum 不存在于 Map 中，则返回 0（你提供的默认值）。

及先判断sum是否存在于map中，存在则返回其对应的下标即value，不存在返回自己提供的默认值，这里是0，可以实现在遍历key值下对应的value的增加、计数

代码

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        //创建一个map来收集A+B和他们出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < ; i++) {
            for (int j = 0; j < ; j++) {
                int tmp = nums1[i] + nums2[j];
                //判断tmp是否出现在map中，默认是0，key对应的value＋1
                (tmp, (tmp, 0) + 1);
            }
        }
        //创建一个计数器用来收集满足条件的组数
        int count = 0;
        //遍历C+D，同时判断0-（C+D）是否存在于map中
        //存在则count加上对应的value
        for (int x :
                nums3) {
            for (int y :
                    nums4) {
                int tmp2 = 0-(x + y);
                if ((tmp2)){
                    count+=(tmp2);
                }
            }
        }
        return count;
    }

3.标准实现

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                (sum, (sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += (0 - i - j, 0);
            }
        }
        return res;
    }
}

区别

标准代码更简洁

4.题目总结

先预处理前两个数组，放在map中，再预处理后两个数组，再在map查是否有我们想要的元素。

383.赎金信

题目链接：赎金信

1.解题思路

使用map

//储存magazine中的字符及次数
//遍历ransomNote,判断map中是否有ransomNote中的字符
//没有则直接false
//如果有则value-1，当value==-1时，返回false

2.我的实现

 public boolean canConstruct(String ransomNote, String magazine) {

        Map<Character,Integer> map=new HashMap<>();
        //储存magazine中的字符及次数
        for (char x:
             ()) {
            (x,(x,0)+1);
        }
        //遍历ransomNote,判断map中是否有ransomNote中的字符
        //如果有则value-1，当value==-1时，返回false
        char[] array=();
        for (char y:
             array) {
            if ((y)){
                (y, (y,0)-1);
            }else {
                return false;
            }
            //如果ransomNote中有多个一样的，将map中的减完了就执行下面
            if ((y)==-1){
                return false;
            }
        }
        //都执行完了就true
        return true;
    }

3.标准实现

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (() > ()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : ()){
            record[c - 'a'] += 1;
        }

        for(char c : ()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

区别

标准中使用数组作为映射表更加简单有效，只是字母时可以考虑数组代替map。

key值可以用数组中的下标代替

4.题目总结

这个题目考察了字符串操作和字符频率统计的基本技巧。解决方法的核心是确保 magazine 中的字符能够满足 ransomNote 中的需求。通过频率统计，可以在一次遍历内解决这个问题，有效地提升了算法的性能。

15.三数之和（！！！）

题目链接：三数之和

1.解题思路

map去重有点麻烦

采用双指针法：需要给数组排序，遍历i位置，指定left在i前一个，right在最后一个，和大于0，那right就向左移，和小于0，left就向右移，直到等于0，或者遍历完

但是三个指针处都要去重

2.我的实现

实现遇到的问题

怎么去重：

如果判断num[i]==num[i+1],判断i位置的后一个是否相等，会否定结果集中有相等元素的情况

用num[i]==num[i--],判断i位置的前一个元素是否相等，如果相等就不要这个集合了

对left和right的去重，在判断是否符合要求后再去重，相当于是跳过。

代码

public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> result=new ArrayList<>();
            (nums);
            //遍历数组
            for (int i = 0; i < ; i++) {
                if (nums[i]>0){
                    return result;
                }
                //对i去重
                if (i>0&&nums[i]==nums[i-1]){
                    continue;
                }
                int left=i+1;
                int right=-1;
                while (right>left){
                    int sum=nums[i]+nums[left]+nums[right];
                    if (sum>0){
                        right--;
                    } else if (sum<0) {
                        left++;
                    }else {
                        ((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;

    }

3.标准实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        (nums);
	// 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < ; i++) {
	    // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) { 
                return result;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }

            int left = i + 1;
            int right =  - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    ((nums[i], nums[left], nums[right]));
		    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; 
                    left++;
                }
            }
        }
        return result;
    }
}

4.题目总结

1. 双指针法：

  • 固定一个元素后，通过双指针在剩余数组中寻找两个元素，使得这三个元素的和为零。
  • 一般情况下，固定元素使用一个循环，然后双指针分别从剩余部分的开始和结束位置开始移动，以寻找满足条件的三元组。

2. 去重策略：

  • 为了避免重复的三元组结果，需要在遍历数组时进行去重。
  • 对于固定元素，检查当前元素是否与前一个元素相同。如果相同，则跳过，以避免生成重复的三元组。
  • 同样地，对于双指针操作，在移动指针时也需要跳过重复的元素。

18.四数之和（！！！）

题目链接：四数之和

1.解题思路

在三数之和的基础上，再套一个循环

2.我的实现

实现遇到的问题

代码

3.标准实现

 public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null ||  < 4) {
            return result;
        }
        (nums);


        for (int i = 0; i < -3; i++) {

            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }

            for (int j = i + 1; j < -2; j++) {

                // nums[i]+nums[j] > target 直接返回, 剪枝操作
                if (nums[i]+nums[j] > 0 && nums[i]+nums[j] > target) {
                    return result;
                }

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right =  - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        ((nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }

以上代码有一个错误，在第二个循环内进行剪枝时，不应直接return result,return 操作是结束整个函数了，应该break跳出循环，而第一个可以直接return是因为后续的循环也无法满足那个条件，第二是因为在后续移动i后还可以满足条件。

修改后的代码如下：

 public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null ||  < 4) {
            return result;
        }
        (nums);


        for (int i = 0; i < -3; i++) {

            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }

            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }

            for (int j = i + 1; j < -2; j++) {

                // nums[i]+nums[j] > target 直接返回, 剪枝操作
                if (nums[i]+nums[j] > 0 && nums[i]+nums[j] > target) {
                    break;
                }

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right =  - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        ((nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }

4.题目总结

注意return和break的区别

1. 排序的必要性

  • 对数组进行排序是实现该算法的关键步骤。排序后的数组便于使用双指针法查找符合条件的元素，并能有效减少重复的结果。

2. 双指针法的应用

  • 双指针法通过从两端逼近中间的方式来寻找两个元素的和。这种方法在有序数组中非常有效，能在 O(n^2) 的时间复杂度内找到所有符合条件的组合。

3. 去重处理

  • 在多层循环和双指针移动时，必须进行去重处理，以避免输出重复的四元组。这一点非常重要，尤其是在处理类似问题时（如三数之和）。

4. 边界条件

  • 考虑到数组可能不足4个元素的情况，必须在进入主逻辑前进行边界条件检查。
  • 双指针操作时要注意索引的边界，确保指针不越界。

5. 整数溢出问题

  • 当四个数相加时，可能会产生超过 int 类型的数值，因此在计算四元组的和时需要使用 long 来存储，以避免整数溢出。

6. 复杂度分析

  • 算法的时间复杂度为 O(n^3)，适用于中等大小的数据集。在非常大的数据集上，可能需要考虑更复杂的优化或不同的方法。

7. 扩展思考

  • 类似的算法可以扩展到寻找其他固定和的元组（例如三数之和、五数之和等），只需调整循环层数和相应的去重处理。

相关文章