本节内容

454.四数相加II
383. 赎金信
15. 三数之和
18. 四数之和
总结

454.四数相加II※

建议：本题是使用map 巧妙解决的问题，好好体会一下哈希法如何提高程序执行效率，降低时间复杂度，当然使用哈希法会提高空间复杂度，但一般来说我们都是舍空间换时间，工业开发也是这样。

题目链接： https://leetcode.cn/problems/4sum-ii/
文章讲解： https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

https://www.yuanql.top/2023/06/12/02_leetcode/454.%20%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0%20II/

题目分析

哈希表：首先将前两个数组进行遍历，得到的数值乘以-1之后存储到hashmap中，对剩余的两个数组进行遍历，得到数值与hashmap进行比对，由此得到匹配的数值，然后将hashmap中的数值添加进result的结果中。

方案一

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> hashMap = new HashMap<>(); // key: nums1与num2相加的结果； value:此key出现的次数，可能有几个数据
        int result = 0, n = nums1.length, temp = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp = -1 * (nums1[i] + nums2[j]);
                hashMap.put(temp, hashMap.getOrDefault(temp, 0) + 1);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temp = nums3[i] + nums4[j];
                if (hashMap.containsKey(temp)) {
                    result += hashMap.get(temp);
                }
            }
        }

        return result;
    }
}

结果

解答成功:
执行耗时:144 ms,击败了48.15% 的Java用户
内存消耗:42.7 MB,击败了32.62% 的Java用户

分析

时间复杂度：
O( n * n )

空间复杂度：
O( n * n )

代码随想录

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

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

本题解题步骤：

首先定义一个hashmap，key放a和b两数之和，value 放a和b两数之和出现的次数。
遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
最后返回统计值 count 就可以了

时间复杂度: O(n^2)
空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^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>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

383. 赎金信※

建议：本题和 242.有效的字母异位词是一个思路，算是拓展题

题目链接： https://leetcode.cn/problems/ransom-note/
文章讲解： https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

https://www.yuanql.top/2023/06/13/02_leetcode/383.%20%E8%B5%8E%E9%87%91%E4%BF%A1/

题目分析

先将 magazine 中的字符一步步拆分放到 HasMap 中，然后将 ransomNote 中的字符一步步去和 hashMap中的数据去比对，如果全部匹配的上，数据量也够，则没有问题，返回true；否则返回 false 。

方案一

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {

        HashMap<Character, Integer> hashMap = new HashMap<>();
        Character temp = '1';
        for (int i = 0; i < magazine.length(); i++) {
            temp = magazine.charAt(i);
            hashMap.put(temp, hashMap.getOrDefault(temp, 0) + 1);
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            temp = ransomNote.charAt(i);
            if (hashMap.containsKey(temp)) {
                hashMap.put(temp, hashMap.get(temp) - 1);
                if (hashMap.get(temp) == 0) {
                    hashMap.remove(temp);
                }
            } else {
                return false;
            }
        }

        return true;
    }
}

结果

解答成功:
执行耗时:14 ms,击败了14.76% 的Java用户
内存消耗:43 MB,击败了18.74% 的Java用户

分析

时间复杂度：
O( n + m )

空间复杂度：
O( 1 )

代码随想录

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

因为题目所只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组还记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

依然是数组在哈希法中的应用。

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

代码实现

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        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;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

建议：本题虽然和两数之和很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下双指针法的思路，文章中讲解的，没问题哈希法很麻烦。

题目链接： https://leetcode.cn/problems/3sum/
文章讲解： https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

https://www.yuanql.top/2023/03/25/02_leetcode/15.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C/

题目分析

年少无知，尝试使用哈希表的方式来解决此问题，走上去之后，发现其是一个不归路，需要好多好的判断条件，极其复杂，遂未达既返，另寻他路。

重温以前的做题方法，写出如下的方案：
参考的博客为： https://www.yuanql.top/2023/03/25/02_leetcode/15.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C/
本题目中的相关限制较多，具体的逻辑请查看以下代码

方案一

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

        List<List<Integer>> result = new ArrayList<>();

        Arrays.sort(nums);

        int left, right;
        for (int i = 0; nums[i] < 1 && i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] > -nums[i]) {
                    right--;
                } else if (nums[left] + nums[right] < -nums[i]) {
                    left++;
                } else {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[i]);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);

                    while (left < nums.length - 1 && nums[left] == nums[++left]) { // 需要防止越界

                    }
                    while (right > 0 && nums[right] == nums[--right]) { // 需要防止越界

                    }
                }
            }
        }
        return result;
    }
}

结果

解答成功:
执行耗时:27 ms,击败了95.01% 的Java用户
内存消耗:49.9 MB,击败了33.16% 的Java用户

分析

时间复杂度：
O( n * n )

空间复杂度：
O( )

代码随想录

https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

哈希解法

两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。

把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

去重的过程不好处理，有很多小细节，如果在面试中很难想到位。

时间复杂度可以做到O(n^2)，但还是比较费时的，因为不好做剪枝操作。

大家可以尝试使用哈希法写一写，就知道其困难的程度了。

双指针

其实这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。

而且使用哈希法在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长。

接下来我来介绍另一个解法：双指针法，这道题目使用双指针法要比哈希法高效一些，那么来讲解一下具体实现的思路。

动画效果如下：

拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

接下来如何移动left 和right呢，如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

时间复杂度：O(n^2)。

代码实现

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

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

18. 四数之和※

建议：要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。本题思路整体和三数之和一样的，都是双指针，但写的时候有很多小细节，需要注意，建议先看视频。

题目链接： https://leetcode.cn/problems/4sum/
文章讲解： https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

https://www.yuanql.top/2023/03/27/02_leetcode/18.%20%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C/

题目分析

方案一

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

        Arrays.sort(nums);

        int left, right;
        for (int i = 0; i < nums.length - 3; i++) {
            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;
                }
                left = j + 1;
                right = nums.length - 1;
                while (left < right) {
                    if ((long) nums[i] + nums[j] + nums[left] + nums[right] > target) {
                        right--;
                    } else if ((long) nums[i] + nums[j] + nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        List<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[left]);
                        temp.add(nums[right]);
                        result.add(temp);
                        while (left < right && nums[left] == nums[++left]) {

                        }
                        while (left < right && nums[right] == nums[--right]) {

                        }
                    }
                }
            }
        }

        return result;
    }
}

结果

解答成功:
执行耗时:16 ms,击败了50.15% 的Java用户
内存消耗:42.8 MB,击败了46.03% 的Java用户

分析

时间复杂度：
O( )

空间复杂度：
O( )

代码随想录

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

代码实现

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; 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 < nums.length; j++) {

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

                int left = j + 1;
                int right = nums.length - 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 {
                        result.add(Arrays.asList(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;
    }
}

总结※

https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E6%80%BB%E7%BB%93.html

02_1_代码随想录算法训练营18期

#LeetCode #算法训练营

06、第三章哈希表part02

http://yuanql.top/2023/07/18/02_1_代码随想录算法训练营18期/06、第三章哈希表part02/

作者

Qingli Yuan

发布于

2023年7月18日

许可协议

2023年7月18日每日一题--1851. 包含每个查询的最小区间上一篇

2023年7月17日每日一题--415. 字符串相加下一篇

06、第三章 哈希表part02

本节内容

454.四数相加II※

题目分析

方案一

结果

分析

代码随想录

代码实现

383. 赎金信※

题目分析

方案一

结果

分析

代码随想录

代码实现

题目分析

方案一

结果

分析

代码随想录

哈希解法

双指针

代码实现

18. 四数之和※

题目分析

方案一

结果

分析

代码随想录

代码实现

总结※

06、第三章哈希表part02