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

454.四数相加II

题目链接：454.四数相加II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

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

思路

考虑采用哈希表来解决，题目给了四个数组，那么我们可以两两一组，遍历nums1[i] + nums2[j]的各种可能数值，将其存入hashmap中（记为hashmap1），即对每一个可能的相加数值，存储其出现过多少次。nums3[k] + nums4[l]的情况类似，也将相加结果存入hashmap中（记为hashmap2）。

然后遍历hashmap1，对于每一个key值p，在hashmap2中寻找key等于0 - p的键值对，如果找到了，则累加hashmap1[p] * hashmap2[-p]。

C++实现

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> hashmap1, hashmap2;

        for(int i = 0;i<nums1.size();i++){
            for(int j = 0;j<nums2.size();j++){
                hashmap1[nums1[i] + nums2[j]] += 1;
            }
        }

        for(int k = 0;k<nums3.size();k++){
            for(int l = 0;l<nums4.size();l++){
                hashmap2[nums3[k] + nums4[l]] += 1;
            }
        }

        int result = 0;
        for(auto p : hashmap1){
            if(hashmap2.find(-p.first) != hashmap2.end()){
                result += (p.second * hashmap2[-p.first]);
            }
        }
        return result;
    }
};

383. 赎金信

题目链接：383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

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

思路

用哈希表来解决，用hashmap1统计magazine字符串中每个字符及其出现次数，然后用hashmap2统计resomNote字符串中每个字符及其出现次数。

对于hashmap2中的每个键值对，如果hashmap1中不存在对应的键，或者对应的值小于hashmap2中给定的值，说明不能满足题目给出的条件，反之则满足。

这里题目里说了两个字符串都由小写英文字母组成，因此开两个大小为26的数组即可表hashmap。

C++实现

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> hashmap1(26, 0), hashmap2(26, 0);

        for(int i = 0;i<magazine.size();i++){
            hashmap1[magazine[i] - 'a'] += 1;
        }

        for(int i = 0;i<ransomNote.size();i++){
            hashmap2[ransomNote[i] - 'a'] += 1;
        }

        for(int i = 0;i<26;i++){
            if(hashmap1[i] < hashmap2[i]) return false;
        }
        return true;
    }
};

15. 三数之和

题目链接：15. 三数之和

编写一个算法来判断一个数 n 是不是快乐数。

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

思路

n最大为3000，因此最多进行两层循环才能保证不超时。

可以考虑采用哈希表的方式解决。首先遍历一遍数组，用hashmap存下每个数值以及对应的下标index。

然后顺序进行两层遍历，在第二层遍历中，记录此时的二元组的值nums[i] + nums[j]，然后在hashmap中寻找-nums[i] - nums[j]对应的下标，为了保证找到的三元组不重复，这里只记录下标值

大于j的可能情况。

上述思路考虑的是数组中每个数值不会重复的情况，而本题中的数值会重复。

因此hashmap中应存储的是每个数值以及对应的下标数组。

这种思路可以得到下标不重复的三元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, vector<int>> hashmap;

        for(int i = 0;i<nums.size();i++){
            hashmap[nums[i]].emplace_back(i);
        }

        vector<vector<int>> results;
        for(int i = 0;i<nums.size();i++){
            for(int j = i + 1;j<nums.size();j++){
                int target = - nums[i] - nums[j];
                if(hashmap.find(target) == hashmap.end()) continue;
                for(int k = 0;k < hashmap[target].size();k++){
                    if(hashmap[target][k] > j) results.push_back({i, j, hashmap[target][k]}); // 返回的是三元组的下标
                }
            }
        }

        return results;
    }
};

上面是上述思路的代码。

上述的思路中，只能保证找到的三元组index不重复，而不能保证每个三元组之间的数值不重复，举个例子：nums = [0, 0, 0, 0]，如果保证三元组的index不重复，这里可以找出四个三元组组合，但是每个三元组都是[0, 0, 0]，按照题意来说，只有一个不重复的三元组。

可以先对数组进行排序，然后再统计。这时可以用双指针的方式来解决。

还是采用两层循环。第一层循环i，如果发现nums[i] = nums[i - 1]，则直接continue，因为如果nums[i] = nums[i - 1]，此时找到的三元组必定重复。第二层循环，用双指针j和k代替，j指向当前二层遍历的第一个元素，k指向最后一个元素，同样的，如果发现nums[j] = nums[j - 1]，直接continue。因为数组已经排好序，因此对于nums[j] + nums[k]的值，当j增加时变大，当k减少时变小。换成代码，如果nums[j] + nums[k] > -nums[i]，则令k–，如果nums[j] + nums[k] < -nums[i]，则令j++，如果相等，则说明找到了一组三元组，此时还要注意这次找到的三元组是否和上一次找到的三元组重复（防止nums[k]重复）。

C++实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> results;

        for(int i = 0;i<nums.size();i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue; // 保证不重复
            int target = -nums[i];
            int k = nums.size() - 1;

            for(int j = i + 1;j<nums.size();j++){
                if(j > i + 1 && nums[j] == nums[j - 1]) continue; // 保证不重复

                while(k > j && nums[j] + nums[k] > target) k--;

                if(k == j) break;

                if(nums[j] + nums[k] == target){
                    if(results.size() > 0){
                        vector<int> tmp = results[results.size() - 1];
                        if(tmp[0] == nums[i] && tmp[1] == nums[j] && tmp[2] == nums[k]) continue; // 保证不重复
                    }
                    results.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }

        return results;
    }
};

18. 四数之和

题目链接：18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

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

思路

和三数之和的思路是类似的，同样先排序，然后用双指针的方式消除一层循环。同样要注意去重。

用三层循环来遍历，第一层用i遍历时，注意要在nums[i] = nums[i - 1]时continue，因为如果nums[i] = nums[i - 1]，此时找到的四元组必定重复。第二层用j遍历类似，也要在nums[j] = nums[j - 1]时continue。

然后使用我们的双指针k, l。k指向当前循环的第一个元素，l指向最后一个，同样地，要在nums[k] = nums[k - 1]时continue。

因为数组已经排好序，因此nums[k] + nums[l]的值随着k的增大而增大，随着l的减小而减小。

找到nums[k] + nums[l]正好等于target - nums[i] - nums[j]的组合，将其加入result中，这时也要检查result中的最后一个四元组是否和当前{nums[i], nums[j], nums[k], nums[l]}重复，这一步主要是避免nums[l]重复。

注意还有一个坑，数值不要超了int的边界。

C++实现

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> results;

        for(int i = 0;i<nums.size();i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue; // 保证不重复
            for(int j = i + 1;j<nums.size();j++){
                if(j > i + 1 && nums[j] == nums[j - 1]) continue; // 保证不重复

                long long n_target = (long long)target - nums[i] - nums[j]; // 数值不要越界
                int l = nums.size() - 1;
                for(int k = j + 1;k<nums.size();k++){
                    if(k > j + 1 && nums[k] == nums[k - 1]) continue; // 保证不重复
                    while(l > k && nums[k] + nums[l] > n_target) l--;

                    if(l == k) break;
                    if(nums[k] + nums[l] == n_target){
                        if(results.size() > 0){
                            auto tmp = results[results.size() - 1];
                            if(tmp[0] == nums[i] && tmp[1] == nums[j] && tmp[2] == nums[k] && tmp[3] == nums[l])
                                continue; // 保证不重复
                        }
                        results.push_back({nums[i], nums[j], nums[k], nums[l]});
                    }
                }
            }
        }

        return results;
    }
};