07代码随想录训练营day07|哈希表part02

1、LeetCode454

454. 四数相加 II - 力扣（LeetCode）

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        int count = 0;
        // 遍历两个数组，求两数组中两数相加的和，存入哈希map中，key为和的值，value为和出现的次数
        for (int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                if (map.find(nums1[i] + nums2[j]) == map.end()) {
                    map.insert(pair<int, int>(nums1[i] + nums2[j], 1));
                } else {
                    map[nums1[i] + nums2[j]]++;
                }
            }
        }
        // 遍历另外两个数组，求两数组中两数相加的和的相反数，查找哈希map中是否存在，若存在，将value值加入count
        for (int i = 0; i < nums3.size(); i++) {
            for (int j = 0; j < nums4.size(); j++) {
                if (map.find(-(nums3[i] + nums4[j])) != map.end()) {
                    count += map[-(nums3[i] + nums4[j])];
                }
            }
        }
        return count;
    }
};

2、LeetCode383

383. 赎金信 - 力扣（LeetCode）

 用数组实现散列表

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int hash[26] = {0};
        // 将magazine中的字母出现次数存入散列表
        for (int i = 0; i < magazine.length(); i++) {
            hash[magazine[i] - 'a']++;
        }
        // 将ransomNote中出现的字母出现次数在散列表中减去
        for (int i = 0; i < ransomNote.length(); i++) {
            hash[ransomNote[i] - 'a']--;
            // 当散列表中出现次数<0的情况，说明magazine中的字母不能够组成ransomNote
            if (hash[ransomNote[i] - 'a'] < 0) return false;
        }
        return true;
    }
};

用unordered_map实现，但unordered_map耗时更多。

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

3、LeetCode15

15. 三数之和 - 力扣（LeetCode）

双指针法

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());  
        // a = nums[i], b = nums[j], c = nums[k] = -(a + b)
        for (int i = 0; i < nums.size(); i++) {
            // 当a > 0时，不存在满足条件的三元组，直接返回
            if (nums[i] > 0) break;
            // 对a去重
            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) {
                    result.push_back({nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (left < right && nums[left] == nums[left + 1]) 
                        left++;
                    while (left < right && nums[right] == nums[right - 1]) 
                        right--;
                    // 找到满足条件的三元组后，左右指针同时移动
                    right--;
                    left++;
                } else if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return result;
    }
};

4、LeetCode18 

 18. 四数之和 - 力扣（LeetCode）

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++) {
            // 一重剪枝
            if (nums[k] > 0 && nums[k] > target) break;
            // 对k去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                int left = i + 1;
                int right = nums.size() - 1;     
                // 二重剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] > 0) {
                    break;
                }
                // 对i去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }  
                while (left < right) {
                    if ((long)nums[k] + nums[i] + nums[left] + nums[right] == target) {
                        result.push_back({nums[k], nums[i], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if((long)nums[k] + nums[i] + nums[left] + nums[right] < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
};