代码随想录-DAY⑤-哈希表——leetcode 242 | 349 | 202

242

思路

先遍历字符串1，
记录每个字符的个数，
然后遍历字符串2，
挨个减去字符个数，
出现小于零的个数说明字符总数不重合。

时间复杂度：O(n)
空间复杂度：O(1)

代码

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()){
            return false;
        }
        vector<int> table(26, 0);

        for(auto c : s){
            table[c-'a']++;
        }
        for(auto c : t){
            table[c-'a']--;
            if(table[c-'a']<0){
                return false;
            }
        }
        return true;
    }
};

349

思路

先把数组1存到哈希表1中，
然后遍历数组2，
将能在哈希表1中找到的存到哈希表2中，
这样可以去掉重复的，
最后把哈希表2转为数组。

时间复杂度: O(n + m)
空间复杂度: O(n)

代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());
        unordered_set<int> result_set;
        for(auto i : nums2){
            if(nums1_set.count(i)){
                result_set.insert(i);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

202

思路

申请一个哈希表，
每计算一次快乐数，
都将结果存到哈希表中，
如果发现重复结果说明不是快乐数，
如果发现结果值为1说明是快乐数。

时间复杂度: O(logn)
空间复杂度: O(logn)

代码

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

    bool isHappy(int n) {
        unordered_set<int> nums;
        while(n!=1){
            if(nums.count(n)){
                return false;
            }
            nums.insert(n);
            n = getnext(n);
        }
        return true;
    }
};