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

作者：神奇cpp | 2024-08-02 03:19:04

踩

文章目录

今天是哈希表专题的第二天

废话不多说，直接上题目

454.四数相加II

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

题目链接：454. 四数相加 II - 力扣（LeetCode）

题目说明：本题需要考虑四个数组如何组合，加和为0。只需要计算有多少种组合，而不需要写出具体的组合方式。同时，本题认为：对于数组中位置不同的元素a、b，即使a与b的值相同(a == b)，a、b也被视为不同的元素，所以我们不需要“去重”，比如四个数组的元素都是n个0，则认为有不只一个组合，每个组合都是0000、0000···，区别在于不同组合中的0取自数组的不同位置（比如第一个组合的第一个0取自nums1[0]，第二个组合的第一个0取自nums1[1]），这是本题与后面的一道题目 18.四数之和 的不同之处

思路

这道题目解法很巧妙，但是有迹可循：前一篇文章day6中的最后一道题 1.两数之和 思路与本题相似，我们可以参照两数之和中的思路

两数之和中，需要在同一个数组中找到相匹配（a+b == target)的元素a、b的下标，思路是：遍历一遍整个数组，同时创建一个map映射作为哈希表记录遍历过的元素的值和下标。每遍历到一个元素a，就从哈希表中查找是否有相匹配的元素b，即auto it = map.find(target-a)。若b在哈希表中，则返回a和b的下标，即return {i, it->second}，遍历结束；否则，将元素a的值和下标作为键值对，添加到map中，继续遍历

我们把这个思路应用到这道题中：首先遍历数组A、B，使用map记录数组A、B的和(a+b)，然后双层for循环，求数组C、D的和(c+d)，在 map中查找是否存在相匹配的a+b（相匹配指的是a+b+c+d == 0），即auto it = map.find(0-(c+d))。这是一个大概的思路，我们接下来讨论一些细节问题

为什么不用数组或集合作为哈希表

数组作为哈希表乍一看可以，但是本题中a+b的值是没有大小限制的，这就戳到了数组的痛点：键的大小必须有大小限制，因此不能使用数组作为哈希表

集合中只能存储键a+b的值，无法存储a+b出现次数的信息，因此也不能使用集合作为哈希表
map的键值是什么

题目需要求出a+b+c+d == 0的组合数量，而不用列出具体的组合的方式。如果0-(c+d)在map中找到了，即it != map.end()，那么it->second应该是a+b+c+d == 0的组合数量，这个组合的数量等于 a+b=0-(c+d)出现的次数，用下面的例子解释：

若当前c=-1，d=2，那么要从map中找到a+b = 0-(c+d) = -1。map中，a+b = -1共出现了一次：a=1，b=-2，所以当c=-1，d=2时，a+b+c+d == 0这样的组合只有一个，就是a+b=-1出现的次数

通过上述分析可知，我们使用0-(c+d)在map中寻找，需要获得a+b=0-(c+d)的出现次数，因此map的键值对为**<a+b的值val， a+b=val的出现次数>**
能不能只用A构建map，然后再遍历B、C、D三个数组寻找0-(b+c+d)

可以，但是时间复杂度是O(n³)，而我们两两遍历，时间复杂度是O(n²)，因此还是用A、B构建map，然后再遍历C、D更加合适
整体思路

首先遍历数组A、B，使用map记录数组A、B的和(a+b)，key存放a和b两数之和，value存放a和b两数之和出现的次数。然后遍历数组C、D，求数组C、D的和(c+d)，在map中查找是否存在相匹配的a+b（相匹配指的是a+b+c+d == 0），即auto it = map.find(0-(c+d))。如果找到了，即it != map.end()，那么count += it->second（count加上key对应的value），统计这个组合的数量；否则不做处理。遍历完C和D后返回count，这个count就是四个数组中a+b+c+d == 0的组合数量

代码实现

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        // 思路就是先进行两个数组A、B的加法，得到一个哈希表，key为a+b的值，value为这个值出现的次数
        // 然后双层for循环，先对C、D做加法，和为c+d，然后再哈希表中查找0-(c+d)，如果找到了，则这个键对应的值是a+b+c+d=0组合的出现次数
        std::unordered_map<int, int> map;
        for(int a : nums1)
        {
            for(int b : nums2)
            {
                map[a+b]++;
            }
        }
        int count = 0;
        for(int c : nums3)
        {
            for(int d : nums4)
            {
                auto it = map.find(0-(c+d));
                if( it != map.end())
                {
                    count += it->second; 
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度: O(n²)
空间复杂度: O(n²)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n²

383.赎金信

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

题目链接：383. 赎金信 - 力扣（LeetCode）

思路

本题中两个字符串都是用小写字母组成，key的大小是有限制的，所以我们可以使用数组实现哈希表。数组的key是 字符串magazine中的各个字符-‘a’，value是 字符串magazine中的各个字符出现的次数

由于map需要维护红黑树或者哈希表，而且还要做哈希函数，所以很费时，而且map的空间消耗要比数组的大，所以能用数组就不map，使用数组更加简单有效

代码实现

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> record(26, 0);
        if(ransomNote.size() > magazine.size())
        {
            return false;
        }
        // 首先统计magazine中各个字出现的次数
        for(char c : magazine)
        {
            record[c-'a']++;
        }
        // 然后检查这些字符是否能组成ransomNote
        for(char c : ransomNote)
        {
            if(--record[c-'a'] < 0) // 注意是--record，不是record--，要先减再判断
            {
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度: O(n)
空间复杂度: O(1)

15.三数之和

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

题目链接：15. 三数之和 - 力扣（LeetCode）

这道题的测试用例有点癫声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】