您现在的位置是：首页 >技术杂谈 >代码随想录算法训练营第三天（20240127） | 哈希表理论基础，242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和 -[补卡20240209]网站首页技术杂谈

哈希表理论基础

哈希表主要有三类：

1. 数组：索引为键，数组元素为值
2. set：集合
3. map:

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set

242.有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int flag[26] = {0};
        for(int i=0; i<s.size(); i++){
            flag[s[i]-'a']++;
        }
        for(int i=0;i<t.size();i++){
            flag[t[i]-'a']--;
            if(flag[t[i]-'a']<0) return false;
        }
        for(const auto& val:flag){
            if(val!=0) return false;
        }
        return true;
    }
};

349. 两个数组的交集

1. 可以在构建set时直接赋值vector元素

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end()), set2;
        for(const auto& val:nums2){
            if(set1.find(val)!=set1.end()){
                set2.insert(val);
            }
        }
        vector<int> res;
        for(const auto& val:set2){
            res.emplace_back(val);
        }
        return res;
    }
};

202. 快乐数

1. 求和
2. 判断是否循环，用unordered_set

class Solution {
public:
    int getSum(int n){
        int res{0};
        while(n>0){
            res += (n%10)*(n%10);
            n = n/10;
        }
        return res;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        set.insert(n);
        while(true){
            int sum = getSum(n);
            // std::cout<<"sum: "<<sum<<std::endl;
            if(sum==1){
                return true;
            }else if(set.find(sum)!=set.end()){
                return false;
            }
            n = sum;
            set.insert(n);
        }
        return false;
    }
};

1. 两数之和

1. 由于返回的是索引，因此需要保留索引、值两个元素，且是两数之和，使用unordered_map，不用考虑元素重复，因为如果满足，必有一个元素在map中，一个是当前遍历的

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        vector<int> res;
        for(int i{0}; i<nums.size(); i++){
            int r = target - nums[i];
            if(map.find(r)!=map.end()){
                res.emplace_back(map[r]);
                res.emplace_back(i);
                return res;
            }else{
                map[nums[i]] = i;
            }
        }
        return res;
    }
};