哈希表C++哈希表详解（知识点+相关LeetCode题目）

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0};//26个英文字符
        for(int i =0 ;i<s.size();i++){
            hash[s[i]-'a']++;
        }
 
        for(int i =0 ;i<t.size();i++){
            hash[t[i]-'a']--;
        }
 
        for(int i =0 ;i<26;i++){
            if(hash[i] != 0){
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> nums1_map(nums1.begin(),nums1.end());
        for(int i=0;i<nums2.size();i++){
            if(nums1_map.find(nums2[i]) != nums1_map.end()){
                //说明是交集
                result.insert(nums2[i]);
            }
        }
 
        return vector<int>(result.begin(),result.end());
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //分别将数值作为key，下标作为value
        unordered_map<int,int> result;
        for(int i =0;i<nums.size();i++){
            auto turn = result.find(target-nums[i]);
            if(turn!= result.end()){
                //存在则返回
                return {turn->second,i};
            }else{
            result.insert(pair<int,int>(nums[i],i));
            }
        }
        return {};
    }
};

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> countAB;
        int count = 0;
        for(int i : nums1){
            for(int j : nums2){
                countAB[i+j]++;//储存起来数值对应的次数
            }
        }
 
        for(int i : nums3){
            for(int j : nums4){
                //因为c++会自动给未创建的键值对自动增加
                int target = 0 - (i+j);
                if(countAB.find(target)!=countAB.end()){
                    count += countAB[target];
                }
            }
        }
 
        return count;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int left=0,right=0;
        vector<vector<int>> result;//定义返回的数组
        sort(nums.begin(),nums.end());
        for(int i = 0;i<nums.size();i++){
            if(nums[i]>0){
                break;//说明已经不可能存在了
            }
 
            if(i>0 && nums[i] == nums[i-1]){
                continue;//去重，该数字如果已经用过了，就不再用了
            }
 
            left = i+1;
            right = nums.size()-1;
             
             
            //基于当前的nums[i]进行后面所有可能的存入result 
            while(left < right){
                int sumNum = nums[i]+nums[left]+nums[right]; 
                if(sumNum > 0){
                    right--;
                }else if(sumNum < 0){
                    left++;
                }else{
                    result.push_back(vector<int>{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;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        //顺序k，i，left，right
        for(int k =0;k<nums.size();k++){
            if(nums[k] > target && nums[k] >=0){
                //剪枝处理--便于执行（只大于不等于--因为等于可能也是一种解法 target 0 0 0）
                //因为只要求k，i，left，right互不相同就可以，去重也是为了防止元素间的对应，就比如当前这个元素使用过了，就不能再使用，两个是分开的意思
                break;
            }
 
            if(k>0 && nums[k]==nums[k-1]){
                continue;//去重
            }
 
            for(int i=k+1;i<nums.size();i++){
                if(nums[i]+nums[k] > target && nums[i]+nums[k] >= 0){
                    //剪枝处理的原理是当前的元素大于target，并且两元素大于0，说明后面不可能成立了（都大于0）
                    break;
                }
 
                //去重一定是从k之后元素开始算，因为这也是i的范围
                if(i>k+1 && nums[i] == nums[i-1]){
                    continue;
                }
 
                int left = i+1;
                int right = nums.size()-1;
 
                while(left <right){
                    long targetNum =(long)nums[k]+nums[i]+nums[left]+nums[right];
 
                    if(targetNum > target){
                        right--;
                    }else if(targetNum < target){
                        left++;
                    }else{
                        result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});
 
                        while(left <right && nums[right]== nums[right-1]){
                            right--;
                        }
                        while(left <right && nums[left]==nums[left+1]){
                            left++;
                        }
 
                        //这里再一步的原因是当前的rightleft仍为之前的rightleft
                        right--;
                        left++;
                    }
                }
            }
        }
 
        return result;
    }
};