立志重刷代码随想录60天冲冲冲！！——第七天

454. 四数相加 II

// 先计算前两个数组各个元素相加的所有情况，统计进哈希表

// 在判断0 - nums3 - nums4是否在表中

我本来以为c++和python一样，初始化是不赋初值的，还多余的写了不存在赋值为1。其实都可以优化掉。

（原版）

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> hashmap;
        // 先计算前两个数组各个元素相加的所有情况，统计进哈希表
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                auto it1 = hashmap.find(nums1[i] + nums2[j]);
                if (it1 == hashmap.end()) {
                    hashmap[nums1[i] + nums2[j]] = 1;
                } else {
                    hashmap[nums1[i] + nums2[j]]++;
                }
            }
        }

        int count = 0; // 统计结果
        // 在判断0 - nums3 - nums4是否在表中
        for (int k = 0; k < nums3.size(); k++) {
            for (int l = 0; l < nums4.size(); l++) {
                auto it2 = hashmap.find(0 - nums3[k] - nums4[l]);
                if (it2 != hashmap.end()) {
                    count += it2->second;
                }
            }
        }
        return count;
    }
};

（优化后）

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> hashmap;
        // 先计算前两个数组各个元素相加的所有情况，统计进哈希表
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                hashmap[nums1[i] + nums2[j]]++; // 优化后
            }
        }

        int count = 0; // 统计结果
        // 在判断0 - nums3 - nums4是否在表中
        for (int k = 0; k < nums3.size(); k++) {
            for (int l = 0; l < nums4.size(); l++) {
                auto it2 = hashmap.find(0 - nums3[k] - nums4[l]);
                if (it2 != hashmap.end()) {
                    count += it2->second;
                }
            }
        }
        return count;
    }
};

383. 赎金信

遍历2次字符串，对比后有负数或不存在为false。秒

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> umap;
        for (char ch: magazine) {
            umap[ch]++;
        }

        for (char ch2: ransomNote) {
            auto it = umap.find(ch2);
            if (it != umap.end()) {
                umap[ch2]--;
                if (umap[ch2] < 0) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
};

15. 三数之和

大体思路是：左右指针，一次遍历，去重

有三个地方需要去重！

一、for循环去重

二三、左右指针去重

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end()); // 排序方法不熟练！！
        
        for (int i = 0; i < nums.size(); i ++) {
            // “第一元素去重”！一定是要 “当前元素” 与 上一元素 “进行比较”，才不会遗漏
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;
                } else {
                    res.push_back(vector<int> {nums[i], nums[left], nums[right]}); // 插入需要用res.push_back(xxx)
                    // “第二元素去重”！！而且需要加在添加元组之后
                    while (left < right && nums[left] == nums[left+1]) left++;
                    while (left < right && nums[right] == nums[right-1]) right--;
                    
                    right--;
                    left++;
                }
            }
        }
        return res;
    }
};

18. 四数之和

写过三数之和，四数之和思路确实好想。

但有几个需要注意的点：

1、第二层循环去重，需要第二次循环才开始比较（与上一次数值比较）

2、而双指针去重，需要与下一次数值进行比较，left++，right--。容易混淆。

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

        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++) {
                // j 需要大于 i+1
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                int left = j + 1;
                int right = nums.size() - 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 {
                        res.push_back(vector<int> {nums[i], nums[j], nums[left], nums[right]});
                        // 做双指针去重，需要比的是下一个位置的数值
                        while (left < right && nums[left] == nums[left+1]) left++;
                        while (left < right && nums[right] == nums[right-1]) right--;
                        left++;
                        right--;
                    }
                }

            }
        }
        return res;
    }
};