LeetCode Hot 100：哈希

LeetCode Hot 100：哈希

1. 两数之和

思路 1：暴力枚举

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                if (nums[i] + nums[j] == target)
                    return {i, j};
        return {-1, -1};
    }
};

思路 2：排序 + 双指针

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<pair<int, int>> comb;
        for (int i = 0; i < n; i++)
            comb.push_back(make_pair(nums[i], i));
        sort(comb.begin(), comb.end(),
             [&](const pair<int, int>& p1, const pair<int, int>& p2) {
                 return p1.first < p2.first;
             });

        int i = 0, j = n - 1;
        while (i < j) {
            if (comb[i].first + comb[j].first == target)
                return {comb[i].second, comb[j].second};
            else if (comb[i].first + comb[j].first > target)
                j--;
            else
                i++;
        }
        return {-1, -1};
    }
};

思路 3：一次遍历 + 哈希

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

49. 字母异位词分组

思路 1：哈希分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        if (strs.empty())
            return {};

        unordered_map<string, vector<string>> hashMap;
        for (string& s : strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hashMap[tmp].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto& [tmp, vec] : hashMap)
            ans.push_back(vec);
        return ans;
    }
};

128. 最长连续序列

思路 1：哈希 + 单向寻找连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty())
            return 0;

        unordered_set<int> hashSet;
        for (int& num : nums)
            hashSet.insert(num);

        int ans = INT_MIN;
        for (auto& num : hashSet) {
            if (hashSet.find(num - 1) == hashSet.end()) {
                int cur = num;
                int cnt = 1;
                while (hashSet.count(cur + 1)) {
                    cur++;
                    cnt++;
                }
                ans = max(ans, cnt);
            }
        }
        return ans;
    }
};

思路 2：哈希 + 双向寻找连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        // 把所有数字放到一个哈希表
        for (int& num : nums)
            hash.insert(num);
        int maxLen = 0;
        while (!hash.empty()) {
            auto cur = *(hash.begin());
            hash.erase(cur);
            int next = cur + 1, prev = cur - 1;
            while (hash.count(next)) {
                hash.erase(next);
                next++;
            }
            while (hash.count(prev)) {
                hash.erase(prev);
                prev--;
            }
            maxLen = max(maxLen, next - prev - 1);
        }
        return maxLen;
    }
};