day7 哈希表2

454.四数相加II

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> umap;
        int res = 0;
        int n = nums1.size();
        for (int num1: nums1) {
            for (int num2: nums2) {
                umap[num1 + num2] ++;
            }
        }
        for (int num3: nums3) {
            for (int num4: nums4) {
                int target = - num3 - num4;
                if (umap.find(target) != umap.end()) {
                    res += umap[target];
                }
            }
        }
        return res;
    }
};

383. 赎金信

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

字母数量有限，因此可以用数组表示，用数组做效率更高：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        vector<int> vec(30, 0);
        for (char ch: magazine) {
            vec[ch -'a'] ++;
        }
        for (char ch: ransomNote) {
            if (vec[ch-'a'] == 0) {
                return false;
            }
            vec[ch-'a'] --;
        }
        return true;
    }
};

15. 三数之和

菜狗哈希版：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        unordered_map<int, vector<int>> umap;
        int n = nums.size();
        for (int i = 0; i < n; i ++) {
            umap[nums[i]].push_back(i);
        }
        for (int i = 0; i < n; i ++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for (int j = i + 1; j < n; j ++) {
                int target = - nums[i] - nums[j];
                if (umap.find(target) != umap.end()) {
                    vector<int> vec = umap[target];
                    for (int index: vec) {
                        if (index > j) {
                            if (res.empty() || res.back() != vector<int>({nums[i], nums[j], nums[index]})) {
                                res.push_back({nums[i], nums[j], nums[index]});
                            }   
                        }
                    }
                }
            }
        }
        return res;
    }
};

有一些过滤条件没有考虑到，比方说第一个数如果>0，就可以return了。优化哈希版不写了，快不了多少。
双指针版：

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

18. 四数之和

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        unordered_map<int, vector<vector<int>>> umap;
        int n = nums.size();
        for (int i = 0; i < n; i ++) {
            for (int j = i + 1; j < n; j ++) {
                int num = nums[i] + nums[j];
                if (umap[num].empty()) {
                    umap[num].push_back({i, j});
                }
                else {
                    int index1 = umap[num].back()[0];
                    int index2 = umap[num].back()[1];
                    if (nums[index1] == nums[i] || nums[index2] == nums[j]) {
                        umap[num].pop_back();
                    }
                    umap[num].push_back({i, j});
                }
            }
        }
        for (int i = 0; i < n; i ++) {
            if (nums[i] > target && nums[i] > 0) {
                break;
            }
            if (nums[n-1] == 1000000000 && nums[n-2] == -1000000000) {
                break;
            }
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            for (int j = i + 1; j < n; j ++) {
                if (j > i + 1 && nums[j] == nums[j-1]) {
                    continue;
                }
                int num =  nums[i] + nums[j];
                if (umap.find((long)target - num) != umap.end()) {
                    cout << umap[(long)target-num].size() << endl;
                    for (auto vec: umap[(long)target - num]) {
                        int p = vec[0];
                        int q = vec[1];
                        if (p > j) {
                            res.push_back({nums[i], nums[j], nums[p], nums[q]});
                        }
                    }
                }
            }
        }
        return res;
    }
};

啥垃圾题啊？一天的好心情都被他搞没了，溢出溢出溢出烦死了，按照测试用例加了个break，不看了，就这么着吧，烦死了