代码随想录算法训练营Day6 | 哈希表part01

遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法

242.有效的字母异位词

leetcode链接
代码随想录链接
一刷状态：通过

思路

思路简单，使用unordered_map实现，统计第一个字符的字母数，再遍历第二个字母对相应的字母数减1，最后再遍历字典查看数量是否都为0。

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char, int> maps;

        for(auto ss:s)
        {
            maps[ss]++;
        }

        for(auto tt:t)
        {
            maps[tt]--;
        }

        for(auto map:maps)
        {
            if(map.second!=0) return false;
        }

        return true;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

349. 两个数组的交集

leetcode链接
代码随想录链接
一刷状态：通过

思路

学习unordered_set 的用法
set.insert() 用于插入数据
set.find() 用于寻找数据
先插入一个数组的数据到unordered_set ，自动去除重复的元素，然后再遍历第二个数组，寻找相同的交集，并插入到另外的unordered_set ，防止重复，最后以vector的结果输出。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set;
        unordered_set<int> resultSet;
        vector<int> result;
        for(auto& nums:nums1)
        {
            set.insert(nums);
        }

        for(auto& nums:nums2)
        {
            if(set.find(nums)!=set.end()) resultSet.insert(nums);
        }

        return vector<int>(resultSet.begin(),resultSet.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

202. 快乐数

leetcode链接
代码随想录链接
一刷状态：通过

思路

理解如何写一个多位数的各个位数的平方和

int m = sum;
int mm = 0;
sum = 0;
while(m!=0)
{
    mm = m % 10;
    sum += mm * mm;
    m = m/10;
}
1
2
3
4
5
6
7
8
9

使用unordered_set 存储相加的和，如果出现与之前相同的sum，则代表会出现循环计算，则返回false，当出现sum==1，即为快乐数，返回true。

class Solution {
public:
    bool isHappy(int n) {
        int sum = n;
        unordered_set<int> set;

        while(1)
        {
            int m = sum;
            int mm = 0;
            sum = 0;
            while(m!=0)
            {
                mm = m % 10;
                sum += mm * mm;
                m = m/10;
            }
            cout<<sum<<endl;
            if(sum==1) return true;
            else if(set.find(sum)!=set.end()) return false;
            else set.insert(sum);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1. 两数之和

leetcode链接
代码随想录链接
一刷状态：未通过（map的find功能不熟悉）

思路

理解map的find功能，这是寻找索引key的函数
所以这道题的解题思路就是，遍历nums，将未能满足 target-nums[i] 的数保存到unordered_map中，然后每次都去判断是否存在 target-nums[i] 的数，直到找到结果。
返回可以使用{a, b}来返回vector。

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};
            }
            else
            {
                map[nums[i]] = i;
            }
        }

        return {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21