代码随想录算法训练营day6 | 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1.两数之和

今天是哈希表专题的第一天

Q：什么时候要用到哈希法？

A：当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

哈希表

哈希表 是一种通过哈希函数将键映射到表中位置的数据结构

哈希表的一些基本定义：

键

定义：

• 键是用来唯一标识哈希表中每个元素的部分。每个键在哈希表中必须是唯一的，即同一个哈希表中不能有两个相同的键。

作用：

• 定位：哈希表使用哈希函数将键转换为哈希值，然后用这个哈希值来决定元素存储的位置（桶/槽）。通过键可以高效地查找、插入或删除对应的元素。
• 冲突解决：如果不同的键映射到同一个位置（即发生冲突），哈希表会使用冲突解决机制（如链表法或开放寻址法）来处理这些冲突。

例子：

在一个学生成绩管理系统中，学生的学号可以作为键，用来唯一标识每个学生的成绩记录

值

定义：

• 值是与每个键关联的数据部分。每个键都对应一个值，值是存储在哈希表中的具体数据。

作用：

• 存储信息：值部分包含了与键相关的实际信息或数据。在哈希表中，通过键可以访问到对应的值。
• 数据访问：当需要查询或操作数据时，通过键可以快速获取到相关的值。

例子：

• 在上述学生成绩管理系统中，学生的成绩可以作为值，存储在与学号关联的哈希表条目中。

实际上，数组就是一张哈希表：数组中的元素是键，它们被存放到数组的不同位置，在数组中可以通过下标直接访问数组中的元素，因此数组是一张哈希表

举个例子，如果想查询一个名字是否在这所学校里，如果使用枚举的话，时间复杂度是O(n)；如果使用哈希表的话，只需要O(1)就能做到

如果使用哈希表存储和查找学生姓名，则在存储信息时把这所学校里学生的名字都存在哈希表里，在查询时通过索引直接就可以知道这位同学在不在这所学校里了

那么如何构建哈希表呢？这就涉及到了哈希函数，哈希函数将键映射到哈希表中的某个位置

哈希函数

还是以“查询一个名字是否在这所学校里”为例，哈希函数将学生的姓名直接映射为哈希表上的索引。通过查询索引下标，我们能快速知道这位同学是否在这所学校里了

哈希函数的设计是哈希表的关键，在存储时，可能出现多个键对应同一个位置，这些键存储在哈希表的同一个位置处，这就是哈希冲突。如果哈希函数设计的不好，则会出现大量的哈希冲突

哈希函数如下图所示，hashCode使用特定的编码方式，把名字转化为数值，这样就把学生名字映射为哈希表上的索引数字了。由于哈希表的大小限制，为了保证映射出的索引数值都落在哈希表上，我们需要对hadhCode(name)取模，这保证了学生姓名一定可以映射到哈希表上

即使哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表中同一个索引下标的位置。我们只能尽量寻找一个计算均匀的哈希函数，避免大量的哈希冲突

哈希冲突

下图展示的就是哈希冲突

如图，小李和小王都映射到了索引下标1的位置，这种现象就是哈希冲突

遇到哈希冲突有两种解决的思路：

• 既然一个位置存不了多个键，那么就在这个位置后面做扩充。具体来说，哈希表的每个位置都指向一个链表的头节点，如果一个键对应到某个位置，则在该位置的链表末尾增加一个节点来存储这个键
• 如果不想做扩展，那么我们就把键放到它对应位置附近的地方。具体来说，当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址，然后把这个键放到这个地址处

上面的两种思路对应哈希冲突的两种解决方案：拉链法 和 线性探测法

拉链法

思想：将所有哈希地址相同的记录存储在一个单链表中，在哈希表中存储的是所有子表的头指针

举例：

小李和小王在索引1的位置处发生了冲突，发生冲突的元素都被存储在索引1的链表中，这样就可以通过索引查找到小李和小王了

注意：拉链法需要选择适当的哈希表大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间

线性探测法

思想：依靠哈希表中的空位来解决冲突。有多种探测空位的方法，这里介绍线性探测方法：当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址，然后把这个键放到这个地址处

为了能容纳所有的数据，一定要保证 哈希表大小 > 数据个数

举例：

同样处理这个冲突，我们从索引1的下一个位置处起，寻找空的哈希位置。索引2的位置是空的，我们可以将小王存放到索引2的位置

常见的三种哈希结构

C++中是怎么使用哈希法解决问题呢？当使用哈希表时，我们一般会选择如下三种数据结构：

• 数组
• set（集合）
• map（映射）

这三种结构的使用方式是依靠键（key）来访问值（value），所以使用这些数据结构来解决映射问题的方法叫作哈希法

集合

红黑树是一种平衡二叉树，所以std::set和std::multiset的键值是有序的。但是键不可以修改，改动键的值会导致整棵树的错乱，所以只能删除和增加

当使用集合解决哈希问题时，优先使用undordered_set，它的查询和增删效率是最优的。如果集合是有序的，那么就用set。如果要求不仅有序还要有重复数据的话，那么就使用multiset

注意：

• **集合中的键值概念与其他数据结构（如映射或字典）中的有所不同。**集合中的每个元素都是一个唯一的“键”。在集合中，元素没有“值”这个概念，因为集合的主要目的是确保元素的唯一性和支持高效的集合操作（如插入、查找和删除），因此键即为值。集合只关心元素的存在性，不关心元素的附加数据或额外信息。

• 虽然std::set和std::multiset 的底层实现基于红黑树而非哈希表，它们通过红黑树来索引和存储数据。不过给我们的使用方式，还是哈希法的使用方式，即依靠键（key）来访问值（value）。所以使用这些数据结构来解决映射问题的方法，我们依然称之为哈希法。std:map同理

映射

同理，std::map和std::multimap的key值也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解——Carl）

注意：在map数据结构中，只对键有特定的要求和限制，而对值则没有限制：

• 键是可比较的，以便能在红黑树中进行排序和查找操作，键必须能实现某种比较接口（例如在 C++ 中，键类型需要实现 < 运算符；在 Java 中，键类型需要实现 Comparable 接口）
• 键是不可重复的（std::map、std::unordered_map）
• 键是不可修改的，否则会扰乱红黑树的平衡结构（std::map、std::multimap）或者 会破坏哈希表的数据结构和性能（std::unordered_map）

值可以是任何数据类型，没有必须实现特定接口或运算符的要求。因为在map中，值只是与对应的键一起存储，不参与树结构的比较和排序操作

举例：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    // 插入键值对
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";

    // 打印 map 中的所有元素
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在这个例子中：

• 键是整数类型，必须能够进行比较操作（红黑树需要对键进行排序和查找）
• 值是字符串类型，可以是任意数据类型（没有特定要求）

C++实现

上面给出了C++标准库的集合和映射的实现方法。除此之外，还有hash_set hash_map，它们是由民间高手自发造的轮子（C++11标准之前造的）。实际上，hash_set hash_map与unordered_set，unordered_map的功能是一样的，但是unordered_set在C++11的时候被引入标准库了，而hash_set并没有，所以建议还是使用unordered_set比较好

std::unordered_set

特点：

• 元素无序
• 插入、删除和查找操作的平均时间复杂度为 O(1)
• 元素唯一

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet;

    // 插入元素
    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(8);
    mySet.insert(1);

    // 打印集合中的元素
    for (const int& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // 查找元素
    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Element found: " << *it << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}
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

std::map

特点：

• 键自动排序
• 插入、删除和查找操作的时间复杂度为 O(log⁡n)
• 键唯一，值可重复

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    // 插入键值对
    myMap[1] = "one";
    myMap[2] = "two";
    myMap[3] = "three";
    // pair函数构造键值对，存储到map容器中
    myMap.insert(std::pair<int, std::string>(4, "four"));

    // 打印键值对
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 查找键
    // find函数返回一个迭代器，指向包含指定键的元素，返回类型是 std::map<Key, T>::iterator
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}
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

小结

直接贴上Carl的总结

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

今天的四道题很好，覆盖了三种哈希结构：数组、集合、映射

242.有效的字母异位词

题目链接：242. 有效的字母异位词 - 力扣（LeetCode）

这道题使用数组作为哈希表，数组作为哈希表在遍历上很方便

思路

数组其实就是一个简单哈希表，既然题目中字符串只有小写字符，那么就定义一个大小为26的数组record，用来统计字符串s、t中各种字符出现的次数。哈希函数：hash(key) = key-'a'

首先使用record统计字符串s中的各个字符：遍历字符串s，根据哈希函数，令record[key-‘a’]++

然后再统计字符串t中的各个字符。可以使用一个新的数组来统计，也可以使用原数组，我们使用原数组：遍历字符串t，根据哈希函数，令record[key-‘a’]–

经过上述统计，如果字符串s和字符串t是异位词，那么record数组的所有元素都应该为0。record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false

代码实现

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 统计两个字符串中各个字符出现的次数，依次比较即可
        // 设计hash函数为key-'a'，哈希表（数组）大小为0~25
        std::vector<int> record(26, 0);
        for(char c : s)
        {
            record[c-'a']++;
        }
        for(char c : t)
        {
            record[c-'a']--;
        }
        // 检查record中的所有元素
        for(int count : record)
        {
            if(count != 0)
            {
                return false;
            }
        }
        return true;
    }
};
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

• 时间复杂度: O(n)
• 空间复杂度: O(1)

这道题的思路很简单，主要复习一下字符串的遍历和数组的定义

复习

数组定义和操作

C++中，std::vector<int> 可以用来定义一个动态数组

#include<iostream>
#include<vector>
int main()
{
    // 1.数组的定义
    std::vector<int> array1;	// 定义一个空的vector
    std::vector<int> array2 = {10, 20, 30, 40, 50};	// 使用初始值列表初始化vector
    std::vector<int> array3(5, 0);	// 定义一个大小为5的vector，所有元素初始化为0
    std::vector<int> array4(array3.begin(), array3,end());	//	范围构造函数，用array3创建array4
    
    // 2.访问和修改元素
    std::vector<int> myVector = {1, 2, 3, 4, 5};
    // 访问元素
    std::cout << "Element at index 2: " << myVector[2] << std::endl;
    // 修改元素
    myVector[2] = 10;
    std::cout << "Element at index 2 after modification: " << myVector[2] << std::endl;
    
    // 3.增加和删除元素(都是在末尾增删)
    // 添加元素
    myVector.push_back(4);
    myVector.push_back(5);
	// 移除最后一个元素
    myVector.pop_back();
    
    // 4.删除所有等于val的元素
    // 使用 std::remove 移动所有等于 val 的元素到末尾，返回指向移除操作后容器的逻辑末尾（不含所有val元素的容器末尾）
    auto new_end = std::remove(vec.begin(), vec.end(), val);
    // 使用 vector::erase 移除这些元素
    vec.erase(new_end, vec.end());
    
    // 5.删除第index位的元素
    if (index < vec.size()) {
        // 使用 vector::erase 删除第 index 位的元素
        vec.erase(vec.begin() + index);
    } else {
        std::cout << "Index out of bounds." << std::endl;
    }
    
    // 6.使用迭代器遍历 vector
    for (std::vector<int>::iterator it = myVector.begin(); it != myVector.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}
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
39
40
41
42
43
44
45
46
47

范围for循环

C++11引入了范围for循环，用于遍历容器，基本语法：

for (declaration : expression) {
    // loop body
}
1
2
3

• declaration：声明一个变量，这个变量在每次迭代中都会被赋值为当前元素。

• expression：一个表达式，返回一个可迭代的范围，例如数组、容器（如 std::vector）、初始化列表等。

for(int count : array)
{
    // loop body
    	 ···
}
1
2
3
4
5

相当于

for(int i=0; i<arrat.size(); ++i)
{
    count = array[i];
    // loop body
         ···
}
1
2
3
4
5
6

349. 两个数组的交集

Carl建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set

题目链接：349. 两个数组的交集 - 力扣（LeetCode）

这道题目用集合作为哈希表，集合能对元素做去重，而元素是无序的

使用数组实现哈希表的情况

这道题可以使用数组吗？不可以，使用数组来做哈希的题目，是因为题目都限制了数值的大小，比如上一道题限制字符串中都是小写字母，key只有26种，而本题没有限制数值的大小，就无法使用数组做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费

思路

题目说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序

如果使用集合，C++提供了三种可用的数据结构：

• std::set
• std::multiset
• std::unordered_set

我们该选择哪一个？

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set

代码实现

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        std::unordered_set<int> result_set; // 存放结果，定义为set是为了去重
        for(int num : nums2)
        {
            // 使用std::find函数在nums1中查找num
            if(find(num1.begin(), nums1.end(), num) != nums1.end())
            {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

std::find是C++标准库中的一个通用查找算法，用于在给定范围内查找指定元素。它接受两个迭代器作为参数，分别表示搜索范围的起始和结束位置。如果找到指定元素，则返回指向该元素的迭代器；否则，返回指向搜索范围末尾的迭代器。可以用于查找数组的元素 或 链表的节点

我们也可以先对其中一个数组进行去重，然后再求交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        std::unordered_set<int> result_set;	// 存放结果，定义为set是为了去重
        std::unordered_set<int> num_set(nums1.begin(), nums1.end());	// 先对nums1做去重
        for(int num : nums2)
        {
            if(num_set.find(num) != num_set.end())
            {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 时间复杂度: O(n + m) m 是最后要把 set转成vector
• 空间复杂度: O(n)

使用set实现哈希表的情况

那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时，在数据量大的情况，差距是很明显的

202. 快乐数

建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子

题目链接：202. 快乐数 - 力扣（LeetCode）

本题使用集合作为哈希表

思路

这道题的难点在如何判断是否进入了无限循环，出现无限循环一定是因为sum重复出现了。我们可以通过判断sum是否重复，进而判断是否进入了无限循环

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了

所以这道题目使用哈希法，来判断sum是否重复出现

除此之外，本题还有一个难点：需要对数值各位做取数操作

代码实现

class Solution {
public:
    int getSum(int n)
    {
        int sum = 0;
        while(n != 0)
        {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1)
        {
            int sum = getSum(n);    // 各位求和
            if(sum == 1)
            {
                return true;
            }
            // 检查sum是否曾经出现过，如果出现过，则陷入了死循环
            if(set.find(sum) != set.end())
            {
                return false;
            }else
            {
                set.insert(sum);
            }
            n = sum;    // 进行下一轮循环
        }
    }
};
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

1.两数之和

建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。

题目链接：1. 两数之和 - 力扣（LeetCode）

本题使用map作为哈希表

思路

• 为什么会想到用哈希法？

  当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

  这道题只需要遍历一趟数组，需要用一个集合记录我们遍历过的元素。定义：若元素1+元素2=target，则称元素1与元素2相匹配。当我们遍历到一个元素a时，我们查询集合中是否有与该元素a相匹配的元素b。这符合哈希法的使用原则：需要查询一个元素是否出现过，或者一个元素是否在集合里

• 哈希表为什么用map

  • 数组作为哈希表的局限：数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

  • set集合作为哈希表的局限：set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用

  • 使用map作为哈希表的原因：本题不仅需要知道元素是否遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适

  那么我们该选择哪种类型的map？

  映射	底层实现	是否有序	数值是否可以重复	能否更改数值	查询效率	增删效率
  std::map	红黑树	key有序	key不可重复	key不可修改	O(log n)	O(log n)
  std::multimap	红黑树	key有序	key可重复	key不可修改	O(log n)	O(log n)
  std::unordered_map	哈希表	key无序	key不可重复	key不可修改	O(1)	O(1)

  **本题不需要key有序，选择std::unordered_map效率更高！**因此选择std::unordered_map实现map

• map用来做什么

  在遍历数组的过程中，map需要记录我们访问过的元素的值和对应的下标，这样才能找到与当前元素a相匹配的元素b，并获得元素b的下标

• map中key和value分别表示什么

  map使用key寻找value。在数组的遍历过程中，我们需要判断 与当前元素a相匹配的 元素b是否出现过，即b=taregt-a是否在集合中。若元素b出现过，则返回元素b的下标。我们使用元素b的值寻找元素b的下标，因此map的存储结构为：

  • key：数组元素值
  • value：数组元素对应的下标

• 整体思路

  遍历数组时，只需要在map中查询是否有和当前遍历到的元素a相匹配的元素b，具体来说，为auto it = map.find(target-a)。

  • 如果元素b在map中，即it != map.end()，则找到了对应的匹配对，返回元素a、b的下标{i, it.second}
  • 如果没有找到元素b，则需要把当前遍历的元素a存放到map中，即map.insert(pair<int, int>(a, i))，这样map存放的就是我们访问过的元素，然后继续遍历数组

  过程如下：

  

  

代码实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 返回匹配上的两个元素的下标
        // 定义一个map，用来存放在数组遍历过程中，见过的所有元素
        // 然后每次遍历到一个新的元素时，都查询traget-该元素 是否在map中
        // 如果在map中，则返回；否则，将该元素直接加入到map中
        std::unordered_map<int, int> map;
        for(int i=0; i<nums.size(); ++i)
        {
            auto it = map.find(target-nums[i]);
            if(it != map.end())
            {
                return {it->second, i};
            }else
            {
                map.insert(pair<int, int>(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

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结

今天是哈希表专题的第一天，复习了哈希表的基本知识，学习了哈希法的思想：当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。学习了 数组、集合、映射实现哈希表的方法和基本操作，以及C++中如何实现这些数据结构。今天的四道题覆盖了这三种哈希结构，可以总结一下三种结构的优缺点：

• 数组：

  • 优点：数组作为哈希表在遍历上很方便
  • 缺点：数组的大小是受限制的，所以要处理的数据是有大小限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

• 集合：

  • 优点：集合能对元素做去重，当需要对数据进行去重处理时，可以考虑使用集合。集合对处理的数据没有大小限制

  • 缺点：set是一个集合，里面放的元素只能是一个key。实际上，集合没有“值”的概念，或者说 键就是值。因此想要存放一些与键相关的信息，就不能使用集合。另外，直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

    不要小瞧 这个耗时，在数据量大的情况，差距是很明显的

• 映射：

  • 优点：映射对数据大小没有限制，如果想要存放与键相关的信息，就需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适
  • 缺点：内存开销大。由于维护树结构或哈希表的开销，映射在某些操作上（如遍历、批量插入）比数组和集合慢

除此之外，还复习了迭代器、范围for循环、vector容器的操作，std::find函数 和 std::pair函数

第三、四道题一开始看不出要使用哈希法，我们将问题分析后转化，发现需要查找元素是否在集合中，适合哈希法的使用情况，因此使用哈希法，然后进一步分析使用哪种结构（数组、集合、映射）实现哈希表。这种分析问题，转化问题的能力很重要