力扣 hot100 - 哈希

624 words

3 minutes

力扣 hot100 - 哈希

2026-02-23

hot100

1. 两数之和#

暴力#

看到 $nums$ 的长度只有 $10^4$ 考虑 $O(n^2)$ 的暴力，枚举数组中任意两数加和看等不等于 $target$ 。

代码：

1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        int n = nums.size();
5
        for (int i = 0; i < n; i++) {
6
            for (int j = 0; j < i; j++) {
7
                if (nums[i] + nums[j] == target) return {i, j};
8
            }
9
        }
10
        return {1, 1, 4, 5, 1, 4};   //理论上一定有解所以出不了循环，但是这里不return，会编译错误
11
    }
12
};

哈希#

上面的做法太暴力了，我们想一下有没有什么办法做做优化。

考虑到我们可以把遍历过的数存到一个哈希表中，表里记录的是他的位置，那么我们在遍历到后面的数字 $x$ 的时候，我们只需要看 $target-x$ 在不在表里就好了，如果不在的话就把 $x$ 丢到表里继续往下遍历，这样我们就能把时间复杂度降到 $O(n)$ 。

代码：

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

49. 字母异位词分组#

其实做法在第一个样例的解释中已经写的差不多了，给相同字母的字符串分组开哈希，对每个字符串排个序往哈希表里对一下就行，很暴力的解法，时间复杂度上也过得去。

代码：

1
class Solution {
2
public:
3
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
4
        unordered_map<string, vector<string>> mp;
5
        for (auto s : strs) {
6
            string t = s;
7
            ranges::sort(s);
8
            mp[s].push_back(t);
9
        }
10
        vector<vector<string>> ans;
11
        for (auto& [k, v] : mp) ans.push_back(move(v));
12
        return ans;
13
    }
14
};

128. 最长连续序列#

元素范围是 $10^9$ 挨个数去暴力扩展肯定不中，那接下来思考怎么快速找连续段。

首先考虑到，连续段肯定有个头，如果我们抓着这个头去进行扩展会不会好很多，那我们怎么找到这个头呢？

我们只需要把数组塞进哈希，对于元素 $x$ ，看 $x-1$ 在不在表里就行了。如果不在说明 $x$ 就是一个连续段的头，我们对于这样的头做扩展，看 $x+1$ 、 $x+2$ 等等在不在表里。对于每个连续段记一下长度即可。

代码：

1
class Solution {
2
public:
3
    int longestConsecutive(vector<int>& nums) {
4
        unordered_set<int> s;
5
        for (auto i : nums) s.insert(i);
6
        int ans = 0;
7
        for (auto st : s) {
8
            if (s.count(st - 1)) continue;
9
            int ed = st + 1;
10
            while (s.count(ed)) ed++;
11
            ans = max(ans, ed - st);
12
        }
13
        return ans;
14
    }
15
};