LeetCode哈希表经典题目解析

1. 两数之和

解法分析

1 暴力枚举

  • 时间复杂度：O(n²)
  • 空间复杂度：O(1)
  • 思路：对每个元素x，枚举寻找target-x

2 排序双指针

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)
  • 思路：
    1. 用结构体保存值和原始下标
    2. 排序后从首尾向中间遍历
    3. 根据和与目标值的比较决定移动方向
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
30
31
32
33
34
35
36
37
38
struct A
{
    int value;
    int index;
    A()=default;
    A(int v,int i){value=v;index=i;}
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<A> vec;
        vec.resize(nums.size());
        for(int i =0;i<nums.size();i++)
        {
            vec[i] = {nums[i],i};
        }

        sort(vec.begin(),vec.end(),[](A x,A y){
            return x.value<y.value;
        });

        int left =0, right = vec.size()-1;
        while(left<right)
        {
            int sum = vec[left].value+vec[right].value;
            if(sum<target)
            left++;
            else if(sum>target)
            right--;
            else return {vec[left].index,vec[right].index};
        }

        return {vec[left].index,vec[right].index};
    };
};


3 哈希表

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  • 思路：
    1. 哈希表key存储值，value存储下标
    2. 遍历过程中查找target-x
    3. 没找到则将当前值加入哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hashMap; // 创建哈希表

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i]; // 计算差值
        // 在哈希表中查找差值
        if (hashMap.find(complement) != hashMap.end()) {
            return {hashMap[complement], i}; // 找到返回下标
        }
        hashMap[nums[i]] = i; // 存入哈希表
    }

    return {}; // 没有找到返回空数组
}

};


49. 字母异位词分组

解法分析

哈希表法

  • 时间复杂度：O(nklogk)，k是字符串的最大长度
  • 空间复杂度：O(nk)
  • 思路：
    1. key为排序后的字符串
    2. value为原始字符串数组
    3. 最后遍历哈希表整理结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string,vector<string>> mp;
        for(auto & str: strs)
        {
            auto s = str;
            sort(str.begin(),str.end());
            mp[str].emplace_back(s);
        }
        vector<vector<string>> ret;
        for(auto & kv: mp)
        {
            ret.emplace_back(kv.second);
        }
        return ret;
    }
};


128. 最长连续序列

解法分析

哈希集合

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)
  • 思路：
    1. 将所有数字加入集合
    2. 遍历每个数x，寻找x+1, x+2…和x-1, x-2…
    3. 边遍历边从集合中删除
    4. 维护最大长度
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
30
31
32
33
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st;
        int count = nums.size();
        for(int i = 0;i<count;i++)
        {
            st.insert(nums[i]);
        }
        int maxlen = 0;
        while(!st.empty())
        {
            int num = *(st.begin());
            st.erase(num);
            
            int cnt = 1;
            int a=1,b=1;
            while(st.find(num+a)!=st.end())
            {
                st.erase(num+a);
                cnt++;    a++;
            }
            while(st.find(num-b)!=st.end())
            {
                st.erase(num-b);
                cnt++;    b++;
            }
            maxlen = max(cnt,maxlen);

        }
        return maxlen;
    }
};