LeetCode Hot100 HashMap

Posted on

两数之和

Problem

https://leetcode.cn/problems/two-sum/?envType=study-plan-v2&envId=top-100-liked

Solution

遍历数组，判断前面的数中有没有target-num有的话就找到了目标数对，用map存一下遍历过的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num2idx;
        for (int i = 0; i < nums.size(); i ++)
        {
            if (num2idx.count(target-nums[i]))
            {
                return {num2idx[target-nums[i]], i};
            }
            num2idx[nums[i]] = i;
        }
        return {-1, -1};
    }
};

字母异位词分组

Problem

https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked

Solution

将排序后字符串作为key。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (string &str : strs)
        {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].push_back(str);
        }
        vector<vector<string>> ans;
        for (pair<string, vector<string>> p : mp)
        {
            ans.push_back(p.second);
        }
        return ans;
    }
};

最长连续序列

Problem

https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

Solution

数组去重，枚举每个数，在num-1不在数组中时，计算以num为开头，连续的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet;
        for (int i = 0; i < nums.size(); i ++)
        {
            numSet.insert(nums[i]);
        }

        int ans = 0;

        for (int num : numSet)
        {
            if (numSet.count(num-1) == 0)
            {
                int tempNum = num;
                int count = 0;
                while (numSet.count(tempNum))
                {
                    tempNum ++;
                    count ++;
                }

                ans = max(ans, count);
            }
        }
        return ans;
    }
};