383. 赎金信

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> umap;
        for (auto i : magazine) umap[i] ++;
        for (auto i : ransomNote) umap[i] --;
        for (auto [x, y] : umap) if (y < 0) return false;
        return true;
    }
};

454. 四数相加 II

把nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0变换下,成了nums1[i] + nums2[j] == -(nums3[k] + nums4[l])

然后两个O(n^2)计算哈希

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> umap1, umap2;
        for (int x1 : nums1)
            for (int x2 : nums2)
                umap1[x1 + x2] ++;
        for (int x1 : nums3)
            for (int x2 : nums4)
                umap2[x1 + x2] ++;
        int res = 0;
        for (auto&[x, y] : umap1)
        {
            if (umap2.count(-x))
            {
                res += y * umap2[-x];
            }
        }
        return res;
    }
};

15. 三数之和

一开始试着哈希写法，发现很折磨，换成了常规的双指针写法。

因为target是0，所以这里第一个可以判定：大于0就永远也不会产生答案了（排序后）。

同时第一个元素相同可以去重操作。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> res;
        for (int i = 0; i < n; i ++)
        {
            if(nums[i] > 0) return res;
            if (i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i + 1, R = n - 1;
            while (L < R)
            {
                if (nums[i] + nums[L] + nums[R] > 0) R --;
                else if (nums[i] + nums[L] + nums[R] < 0) L ++;
                else
                {
                    res.push_back({nums[i], nums[L], nums[R]});
                    while (L + 1 < n && nums[L] == nums[L + 1]) L ++;
                    while (R - 1 >= 0 && nums[R] == nums[R - 1]) R --;
                    L ++, R --;
                }
            }
        }
        return res;
    }
};

18. 四数之和

target不是0，不可以特判。

不过可以相同continue，具体表现在

if (i > 0 && nums[i] == nums[i-1]) continue;
if (j > i + 1 && nums[j] == nums[j-1]) continue;

这两题都要注意最内层要while去重

while (L < n-1 && nums[L] == nums[L+1]) L ++;
while (0 < R && nums[R] == nums[R-1]) R --;

整体的代码如下

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i ++)
        {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i + 1; j < n; j ++)
            {
                long long x = nums[i] + nums[j];
                if (j > i + 1 && nums[j] == nums[j-1]) continue;
                int L = j + 1, R = n - 1;
                while (L < R)
                {
                    if (x + nums[L] + nums[R] < target) L ++;
                    else if (x + nums[L] + nums[R] > target) R --;
                    else
                    {
                        res.push_back({nums[i], nums[j], nums[L], nums[R]});
                        while (L < n-1 && nums[L] == nums[L+1]) L ++;
                        while (0 < R && nums[R] == nums[R-1]) R --;
                        L ++, R --;
                    }
                }
            }
        }
        return res;
    }
};