代码随想录算法训练营 DAY7 | 哈希专题

 leetcode 四数之和https://leetcode.cn/problems/4sum-ii/submissions/

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> map1;
        unordered_map<int,int> map2;
        int size=nums1.size();
        int ans=0;
 
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                map1[nums1[i]+nums2[j]]++;
            }
        }
 
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                map2[nums3[i]+nums4[j]]++;
            }
        }
 
        for(auto it1=map1.begin();it1!=map1.end();it1++){
            for(auto it2=map2.begin();it2!=map2.end();it2++){
                if(it1->first + it2->first==0){
                    ans+=it1->second * it2->second;
                }
            }
        }
 
 
        return ans;
 
    }
};

解析： 利用hashmap当中间储存器，分别把前两段的和，和后两段的和统计出来，再遍历两个hashmap来确定四数之和。以空间换时间，要么一个数只是要匹配四层循环。

leetcode 赎金信https://leetcode.cn/problems/ransom-note/submissions/

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

解析： 其实这道题和leetcode 242 一样的，本质思想都是分门别类把，还是桶思想，把相同的属性放在一个桶里面，没什么特别之处。

 leetcode 三数之和https://leetcode.cn/problems/3sum/submissions/

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if (nums[i] > 0) {
                return ans;
            }
 
            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{
                    ans.push_back({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 ans;
    }
};

解析：这道题真的是让我绷不住了，刚开始的没有一点思路，不知道从何开始筛选寻找这三个数。

接着就是想到暴力算法，三层for循环vector直接收集所有的答案，最后hashmap去重。然后想你三层for循环能干的事情，我hashset以空间换时间两层for循环给你搞定。结果，我擦，怎么去重？，通常的hashset以空间换时间，最多是统计次数。收集所有不重复的结果。去重是真的复杂。

难道，难道我只能使用最后的必杀技了嘛，我从脑海深处，慢慢拔出双指针这把利剑，双指针？巧妙的使用两个指针，在数组间移动，竟然能达到减少多层for循环的效果。我该怎么用？？！！，啊啊，要长出脑子了。。。

冥冥之中，有个声音在脑海中回荡。。。

双指针搭配排序才能发挥出巨大的威力，双指针的根本在于，利用顺序，对比，不断的移动，扩张，收缩。

我懂了，以雷霆击碎黑暗！！ i为第一层for遍历， left， right 指针，分别为i+1 ，length-1。第一层i是地毯式搜索，left 和right 区间内寻找正确答案。

leetccode 四数之和https://leetcode.cn/problems/4sum/

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]>target&&nums[k]>=0&&target>=0) break;
            if(k>0&&nums[k]==nums[k-1]) continue;
            for(int i=k+1;i<nums.size();i++)
            {
                if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0&&target>=0) break;
                if(i>k+1&&nums[i]==nums[i-1]) continue;
            
            int left= i+1,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({nums[k], nums[i], nums[left], nums[right]});
                    while(right>left&&nums[right]==nums[right-1]) right--;
                    while(right>left&&nums[left]==nums[left+1]) left++;
                    right--;
                    left++;
                }
            }
            }
        }
        return result;
    }
};

解析：把i 的一层for循环地毯式搜索，转化为两层for循环地毯式搜索。