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

454.四数相加II

代码随想录链接

题目

LeetCode-454

给定四个数组，计算满足从各个数组中取一个值得到的四个值之和为0的情况有几种。

自己的想法

怎么一上来先想到的是暴力法啊（恼）

因为要求四个数之和是0，且只要求输出可行的对数，可以使用一个map来存储第一个和第二个数组中每种可能的和，然后根据第三个数组和第四个数组中取出的数之和来找在map中是否有相应的数据满足四个数之和为0。

解法

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> addedMap;           // 存储第1个和第2个数组中取出的数的值之和的情况
        int count = 0;                              // 计数有多少种可能满足
        for (int a: nums1) {
            for (int b: nums2) {
                addedMap[a + b]++;                  // 存储和的出现次数
            }
        }
        for (int c: nums3) {
            for (int d: nums4) {
                if (addedMap[0 - (c + d)] != 0) {   // 如果存在a+b满足a+b+c+d==0
                    count += addedMap[0 - (c + d)]; // 计数器增加
                }
            }
        }
        return count;
    }
};

时间复杂度为\(O(n^2)\)，空间复杂度为\(O(n)\)。

383.赎金信

代码随想录链接

题目

LeetCode-383

给定一个字符串ransom和另一个字符串magazine，判断ransom字符串能否由magazine字符串中的字母组成，每个位置上的字母只能使用一次。

自己的想法

使用map统计magazine中每个字符出现的次数，然后再遍历ransom字符串，判断每个字符都在map内存在对应的足够的出现次数。

其实也可以用int record[26] = {0}来存，因为题目说了只有小写字母。

解法

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mapMagazine;               // 用来存储magazine中字符出现次数的map
        for (char m: magazine) {
            mapMagazine[m]++;                               // 遍历magazine字符串，统计字符出现次数
        }
        for (char r: ransomNote) {                          // 遍历ransom字符串
            if (mapMagazine.count(r) <= 0) return false;    // 若map中不存在这个字符，直接判断不满足
            mapMagazine[r]--;                               // 抵消map中这个字符的计数一次
            if (mapMagazine[r] < 0) return false;           // 如果抵消后，计数低于0，证明不满足条件，返回false
        }
        return true;                                        // 满足条件，返回true
    }
};

时间复杂度为\(O(n)\)，空间复杂度为\(O(n)\)。

15.三数之和

代码随想录链接

题目

LeetCode-15

给定一个数组，输出三个位置不相同的数，且这三个数之和为0。

自己的想法

一开始想用哈希做来着，但是哈希感觉还要去重，不是很容易。然后就不知道该咋办了

看了代码随想录的提示，开始往双指针上考虑。这个方法主要是要想好开始的时候左右指针要怎么定义，以及移动指针的条件。

由于题目要求输出三个相加为0的数，所以可以对本题的数组进行排序。遍历数组，并在遍历的数据后方进行左右指针的调整。

解法

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> results;                                                    // 存储最终数组
        sort(nums.begin(), nums.end());                                                 // 对数组进行排序，sort函数默认为升序
        for (int i = 0; i < nums.size(); i++) {                                         // 遍历数组中每个数据
            if (nums[i] > 0) {                                                          // 如果其本身就已经大于0，加上后面的数据必大于0，一定不满足条件
                return results;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {                                      // 如果和左侧相邻的数相同，已经计算过，不用再次计算
                continue;
            }
            int left = i + 1;                                                           // 确定左右区间
            int right = nums.size() - 1;
            while (right > left) {                                                      // 指针不能重合
                if (nums[i] + nums[left] + nums[right] > 0) right--;                    // 如果三个值之和大于0，证明右指针需要朝着变小的方向移动
                else if (nums[i] + nums[left] + nums[right] < 0) left++;                // 如果三个值之和小于0，证明左指针需要朝着变大的方向移动
                else {                                                                  // 如果三值之和等于0
                    results.push_back(vector<int>{nums[i], 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 results;                                                                 // 返回结果
    }
};

18.四数之和

代码随想录链接

题目

LeetCode-18

在一个给定的数组内，找出4个索引不同的数据，使得四个数之和为给定的目标值。

自己的想法

和上面道题非常相似，其实感觉就可以在上面的题解的基础上，增加一个for循环，以两个for循环的索引指向的值之和为确定值，使用双指针法确定剩下两个数。

解法

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;                                                                 // 结果数组
        sort(nums.begin(), nums.end());                                                             // 生序排序
        for (int k = 0; k < nums.size(); k++) {                                                     // 遍历，确定第1个值
            if (nums[k] > target && nums[k] >= 0) {                                                 // 如果本身就是正数且大于目标值，右侧的数只会比这个数大，加起来必定不会满足条件
                break;
            }
            if (k > 0 && nums[k] == nums[k - 1]) {                                                  // 去重
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {                                             // 遍历，确定第2个值
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {                         // 第1个值和第2个值加起来大于目标值且之和为正数，加上右侧的数必定不满足条件
                    break;
                }
                if (i > k + 1 && nums[i] == nums[i - 1]) {                                          // 第2个值去重
                    continue;
                }

                int left = i + 1;                                                                   // 确定左右区间
                int right = nums.size() - 1;
                while (right > left) {                                                              // 双指针循环条件
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) right--;      // 四数之和大于目标值，右指针左移
                    else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) left++;  // 四数之和小于目标值，左指针右移
                    else {                                                                          // 若四数之和等于目标值
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});   // 保存结果
                        while (right > left && nums[left] == nums[left + 1]) left++;                // 左指针指向的值去重
                        while (right > left && nums[right] == nums[right - 1]) right--;             // 右指针指向的值去重

                        right--;                                                                    // 左右指针向中间移动一位
                        left++;
                    }
                }
            }
        }
        return result;                                                                              // 返回结果
    }
};

哈希总结

哈希表在刷题中经常用于快速判断一个元素是否出现在集合里。一些哈希表实现的知识，请参考昨天的总结。

经典题目

• 数组作为哈希表

在昨天和今天的题目里，主要是用于在只会出现的小写字母的字符串判断。这种情况下使用数组要比使用C++的STL要更快一些。

LeetCode-242 有效的字母异位词

LeetCode-383 赎金信

• set作为哈希表

当可能出现的数据的范围比较大时，再使用数组就不合理了，因为数组大小是有限的，而且声明过大的数组会浪费内存。

在昨天的文章中，提到了C++中set的三种数据结构，在不需要排序和数据重复的情况下，使用std::unordered_set是最高效的。

LeetCode-202 快乐数

LeetCode-349 两个数组的交集

• map作为哈希表

相比于set，map适合用在需要记录额外信息的地方，例如，记录了一个元素出现了多少次、记录一个元素的在数组中的下标等等...

map所存储的是键值对，在昨天的文章中，提到了C++中有三种map的数据结构，和set类似，如果不需要对key进行排序和重复的情况下，使用std::unordered_map的效率是最高的。

LeetCode-1 两数之和

LeetCode-454 四数相加II