day6 哈希表1

哈希表理论

哈希表一般用来快速判断一个元素是否出现集合里，时间复杂度为O(1)，用空间换时间。

242.有效的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> vmap(30);
        for (char ch: s) {
            vmap[ch - 'a'] ++;
        }
        for (char ch: t) {
            vmap[ch - 'a'] --;
        }
        for (int num: vmap) {
            if (num != 0) {
                return false;
            }
        }
        return true;
    }
};

349. 两个数组的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> uset;
        unordered_set<int> res;
        for (int num: nums1) {
            uset.insert(num);
        }
        for (int num: nums2) {
            if (find(uset.begin(), uset.end(), num) != uset.end()) {
                res.insert(num);
            }
        }
        return vector<int>(res.begin(), res.end());
    }
};

202. 快乐数

class Solution {
public:
    int getNum(int n) {
        int res = 0;
        while (n) {
            int num = n % 10;
            res += num * num;
            n /= 10;
        }
        return res;
    }

    bool isHappy(int n) {
        unordered_set<int> uset;
        uset.insert(n);
        while (n!= 1) {
            n = getNum(n);
            if (find(uset.begin(), uset.end(), n) != uset.end()) {
                return false;
            }
            uset.insert(n);
        }
        return true;
    }
};

1. 两数之和

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