(C++哈希表01)

242、有效的字母异位词

用数组模拟哈希表

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

时间复杂度：O(n + m);

空间复杂度：O(1)

349、两个数组的交集

set占用空间很大，如果题目中的数据有限，优先使用数组。

unordered_set<int> nums_set(nums1.begin(), nums1.end()); 迭代器初始化

find(key)函数，找到key返回begin()，找不到返回end()

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        //迭代器初始化
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
 
        for(int num: nums2) {
            //找不到num，find()会返回end()
            if(nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
 
        return vector<int>(result_set.begin(), result_set.end());
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

202、快乐数

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> result_set;
        int count = 0;
        result_set.insert(n);
        while(true) {
            while(n > 0) {
                int x = n % 10;
                count += x * x; 
                n /= 10;
            }
            if(count == 1) {
                return true;
            }
            if(result_set.find(count) != result_set.end()) {
                return false;
            }
            result_set.insert(count);
            n = count;
            count = 0;
        }
    }
};

时间复杂度：O(logn)

空间复杂度：O(logn)

1、两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);
            if(iter != map.end()) {
                return {iter->second, i};
            }
            map.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
};

时间复杂度：O(n)

空间复杂度：O(n)