前言

          进行 哈希表刷题训练 ！

一、简介

为什么

对于数组 a[i] = x，下标 i 只能是在某一段范围内的某一个较小的整数，一个数 n 很大或者是实数或者是字符串时就不很难进行通过数组来进行访问。

是什么

哈希表又称为散列表，是一种可以通过任意的关键吗（key）直接进行访问的数据结构。
本质就是将一个复杂信息的集合通过哈希函数映射成一个小的范围的集合作为索引。

组成

哈希表由两部分组成，一个是实现的数据结构，通常是链表（不支持索引来访问）、数组（只能支持一个非常小的整数作为下标）。就引出了另一部分组成，哈希函数，通过输入关键码（key），返回哈希表数据结构的索引，通过将任意一个 key（复杂信息数据，大的整数、实数、字符串）经过哈希函数映射成一个简单小的信息（小的整数）。

对外封装为可以通过关键码直接访问的数据结构：hash_table[key] = value;
实际上是在数据结构的哈希函数 hash(key) 位置存储了 value：data_structure[hash(key)] = value，data_structure 为数组或链表。

处理冲突

1. 将一个大的集合映射成一个小的集合会有冲突（碰撞）。

2. 哈希碰撞：两个不同的 key 计算出同样的 Hash 结果。

3. 解决方法：开散列

   • Hash 函数依然用于计算数组下标
   • 数组的每个位置存储链表的表头指针
   • 每个链表存储具有同样 Hash 值对应要存储的值

4. 完整结构图
   

集合(Set)与映射(Map)

1. 集合与映射是两个用来维护信息的基本数据结构。

2. 集合(set)是一个抽象的概念（一个封装），怎么实现可以通过哈希表也可以通过平衡二叉树来实现，即哈希表和平衡二叉树是内部实现。

   • 集合用来存储不重复的元素
   • 有序集合一般用平衡二叉树来实现，时间复杂度为 O(logN)
   • 无序集合一般用哈希表来实现，时间复杂度位 O(1)

3. 映射（map）也是一个抽象的概念（一个封装），怎么实现可以通过哈希表也可以通过平衡二叉树来实现，即哈希表和平衡二叉树是内部实现。

   • 用来存储不重复的键值对（key-value 对）
   • 有序集合，遍历时按照 key 大小排列，一般用平衡二叉树来实现，时间复杂度为 O(logN)
   • 无序集合一般用哈希表来实现，时间复杂度位 O(1)

二、刷题

LeetCode 1. 两数之和

LeetCode 1. 两数之和 原题链接

思路：

枚举两个的需要先想下是否需要保持顺序，本题以任意顺序返回则 nums[i]+nums[j] 与 nums[j]+nums[i] 没有区别，则自己加一个 j < i 这样的条件便于维护。

代码剖析：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        /* for every num
            search if (target-number) in nums(除去num)
        */

        // j < i
        /*  整体思路：
            for i = 0~n-1
            search if (target - nums[i]) exists in nums[0,i-1]
            nums[0,i-1]可以用哈希表来维护
        */
		// 时间复杂度位 O(n)
        int n = nums.size();
        unordered_map<int, int> val_to_index;
        // 不等于尾部，就是找到了，表示存在
        for (int i = 0; i < n; i ++) {
            if (val_to_index.find(target - nums[i]) != val_to_index.end()) { 
                return {val_to_index[target - nums[i]], i};
            }
            // i每次循环一次，nums[0, i-1]也需要多一个数
            // 边循环i，变插入
            // 本质是在i之前查找，防止查到i本身
            val_to_index[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
22
23
24
25
26
27
28
29
30

LeetCode 49. 字母异位词分组

LeetCode 49. 字母异位词分组 原题链接

方法一：字符串哈希

$(1)$ 哈希表用于分组；
$(2)$ 字符串中字符相同排列不同分到一组；
$(3)$ 排序：将字符串中的字符排序看哪些字符串是一样的然后将这些分到一组；
$(4)$ 分组：以排序后的字符串为 key，以字符串为 value 创建键值对，从 string 到数组的映射；
$(5)$ 时间复杂度 O(nlog)

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 哈希表可用于分组
        // 从排序后的字符串（aet）映射到一个数组（["ate", "eat", "tea"]）的Map
        unordered_map<string, vector<string>> group;

        for (string str : strs) {
            string copy = str;
            // 字符串里面的字符排序
            sort(copy.begin(), copy.end());
            // 分组
            group[copy].push_back(str);
        }
        // 将哈希表变成一个数组
        vector<vector<string>> ans;
        for (auto gr : group) {
            // gr.first = key
            // gr.second = value
            ans.push_back(gr.second);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二

LeetCode 1748. 唯一元素的和 原题链接

class Solution {
public:
    int sumOfUnique(vector<int>& nums) {
        int sum = 0;
        vector<int> heap(105, 0);

        for (auto num : nums) heap[num] ++;
        for (auto num : nums) {
            if (heap[num] == 1) 
                sum += num;
        }
        return sum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 387. 字符串中的第一个唯一字符 原题链接

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> heap(26, 0);
        for (auto c : s) heap[c - 'a'] ++;
        for (int i = 0; i < s.size(); i ++) {
            if (heap[s[i] - 'a'] == 1)
                return i;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

LeetCode 1941. 检查是否所有字符出现次数相同 原题链接

class Solution {
public:
    bool areOccurrencesEqual(string s) {
        vector<int> heap(26, 0);

        for (auto c : s) heap[c - 'a'] ++;
        int v = heap[s[0] - 'a'];

        for (int i = 0; i < 26; i ++) {
            if (heap[i] > 0 && heap[i] != v) 
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode 448. 找到所有数组中消失的数字 原题链接

• 没有空间限制的情况下：开一个长度为 n的 heap数组用来标记 1-n每个数是否出现过，遍历整个 nums数组，标记一下所有出现过的数；之后再从 1-n遍历 heap数组将没有出现过的数输出；
• O(1) 的空间复杂度：对原数组进行修改，如果 x出现过，将 a[x]变成 -a[x]（标记），统计没有改变数的数量；

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (auto x : nums) {
            x = abs(x);
            if (nums[x - 1] > 0) nums[x - 1] *= -1; // 没有标记过，进行标记
        }
        vector<int> ret;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] > 0) 
                ret.push_back(i + 1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode 1512. 好数对的数目 原题链接

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        vector<int> heap(105, 0);
        int ans = 0;

        for (int i = 0; i < nums.size(); i ++) {
            ans += heap[nums[i]];
            heap[nums[i]] ++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13