第5章〓哈希表
 知识图谱




5．1哈希表概述
5．1．1哈希表的定义
1． 哈希表和哈希函数
哈希表也称为散列表，是一种根据键直接进行访问的数据结构，也就是通过把键映射到表中的一个位置来访问元素，以加快查找的速度。这个映射函数称为哈希函数，存放元素的数组称为哈希表。

假设哈希表为ht［0．．MAXH-1］(长度为MAXH)，哈希函数为h。给定一个元素集合，每个元素的键是唯一的，以每个元素的键k为自变量，通过一个哈希函数h把k映射为内存单元的地址(或相对地址)h(k)，并把该元素存储在这个内存单元中。

这样，对于两个不同的键ki和kj(i≠j)可能出现h(ki)=h(kj)，这种现象称为哈希冲突，将具有不同键但哈希函数值相同的元素称为“同义词”，这种冲突也称为同义词冲突。

若对于元素集合中的任意一个元素，经哈希函数映射到哈希地址集合中任何一个地址的概率是相等的，则称该哈希函数为均匀哈希函数，这就是使键经过哈希函数得到一个“随机的地址”，从而减少哈希冲突。

设计哈希函数的常用方法之一是除留余数法，该方法取键被某个不大于哈希表长度MAXH的整数p除后所得的余数为哈希地址，即h(k)=k % p(p≤MAXH)，对p的选择很重要，若p选的不好容易产生同义词，一般取小于或等于MAXH的素数。如图5．1所示为一个哈希表示意图。



图5．1哈希表示意图


2． 解决哈希冲突的方法

解决哈希冲突的方法有许多，可分为开放定址法和拉链法两大类。

1) 开放定址法

开放定址法就是在插入一个键为k的元素时，若发生哈希冲突，通过某种哈希冲突解决函数(也称为再哈希)得到一个新空闲地址再插入该元素的方法。这样的哈希冲突解决函数设计有很多种，下面介绍常用的两种。

(1) 线性探测法。线性探测法是从发生冲突的地址(设为d0)开始，依次探测d0的下一个地址，直到找到一个空闲单元为止。线性探测法的迭代公式为： 
d0=h(k)
di=(di-1+1)%MAXH(1≤i≤MAXH-1)
其中，模MAXH是为了保证试探0~MAXH-1的有效地址，当到达地址为MAXH-1的哈希表的表尾时，下一个探测的地址是表首地址0。

(2) 平方探测法。设发生冲突的地址为d0，平方探测法的探测序列为d0+12，d0-12，d0+22，d0-22，…。平方探测法的数学描述公式为： 
d0=h(k)
di=(d0±i2) % MAXH(1≤i≤MAXH-1)
线性探测法是沿着一个方向循环试探下一个地址，平方探测法是前后试探下一个地址。此外，开放定址法的探测方法还有伪随机序列法、双哈希函数法等。

例如，某个哈希表ht的长度MAXH=8，哈希函数为h(k)=k%7，空位置用键NULLKEY(-1)表示，删除位置用键DELKEY(-2)表示，使用线性探测法解决冲突，求依次插入2、9、16、15和1，删除9，再插入8和16的结果，并求最终哈希表的成功查找和不成功查找的平均查找长度。创建哈希表的过程如下。

(1) 初始哈希表如图5．2(a)所示。

(2) 插入2，h(2)=2%7=2，d0=2，插入ht［2］中(探测一次)； 插入9，h(9)=9%7=2，d0=2，冲突(ht［2］已经被2占用)，使用线性探测法，求出d1=(d0+1)%8=3，插入ht［3］中(探测两次)； 插入16，h(16)=16%7=2，d0=2，冲突，使用线性探测法，求出d1=(d0+1)%8=3，仍冲突，求出d2=(d1+1)%8=4，插入ht［4］中(探测3次)，如图5．2(b)所示。

(3) 插入15，h(15)=15%7=1，d0=1，插入ht［1］中(探测一次)； 插入1，h(1)=1%7=1，d0=1，冲突，使用线性探测法，求出d1=(d0+1)%8=2，仍冲突，一直到d4=5，插入ht［5］中(探测5次)，如图5．2(c)所示。

(4) 删除9，找到ht［3］=9，将该位置的键改为DELKEY，探测次数置为0，如图5．2(d)所示。

(5) 插入8，h(8)=8%7=1，d0=1，冲突，使用线性探测法，求出d1=(d0+1)%8=2，仍冲突，d2=(d1+1)%8=3，ht［3］的键为DELKEY，将8插入ht［3］中(探测3次)，插入16，在ht中找到ht［4］=16，说明键重复，不能插入，如图5．2(e)所示。

此时哈希表中包含n=5个键，其查找成功的平均查找长度(ASL成功)为5个键的平均探测次数，即： 
ASL成功=1+1+3+3+55=2．6
现在求查找不成功的平均查找长度(ASL不成功)，假设给定键x，它不在哈希表中，也需要按照查找过程找到空位置为止。分析哈希函数可知h(x)可能的取值为0~6。

(1) 若h(x)=0，探测一次确定查找失败。

(2) 若h(x)=1，探测6次(依次与ht［1．．6］比较)确定查找失败。

(3) 若h(x)=2，探测5次确定查找失败。

(4) 若h(x)=3，探测4次确定查找失败。

(5) 若h(x)=4，探测3次确定查找失败。

(6) 若h(x)=5，探测两次确定查找失败。

(7) 若h(x)=5，探测一次确定查找失败。

查找不成功的平均查找长度就是所有可能查找失败的平均探测次数，即： 
ASL不成功=1+6+5+4+3+2+17=3．14



图5．2哈希表的操作过程(1)



2) 拉链法

拉链法是把所有的同义词用单链表链接起来的方法(每个这样的单链表称为一个桶)。如图5．2所示，哈希函数为h(k)=k % MAXH，所有哈希地址为i的元素对应的结点构成一个单链表，称为单链表i。哈希表的地址空间为0~MAXH-1，在地址i的单元中存放对应单链表的首结点地址。

例如，某个哈希表ht的长度MAXH=5，哈希函数为h(k)=k%5，使用拉链法解决冲突，求依次插入2、9、16、15、1、6，删除1和9，再插入8和7的结果，并求最终哈希表的成功查找和不成功查找的平均查找长度。创建哈希表的过程如下。

(1) 初始哈希表如图5．3(a)所示。

(2) 插入2、9、16、15、1、6，求出各键的哈希函数值，h(2)=2，h(9)=4，h(16)=1，h(15)=0，h(1)=1，h(6)=1。对于h(k)=i的元素创建一个存放结点p，使用头插法插入单链表i中，按上述顺序插入得到的哈希表如图5．3(b)所示。

(3) 删除1，h(1)=1，在单链表1中找到键为1的结点，删除之； 删除9，h(9)=4，在单链表4中找到键为9的结点，删除之，删除后的哈希表如图5．3(c)所示。

(4) 插入8，h(8)=3，将其插入单链表3中； 插入7，h(7)=2，将其插入单链表2的头部，如图5．3(d)所示。

此时哈希表中包含n=6个结点，查找15、6、7、8均需要比较一次，查找16和2均需要比较两次，其查找成功的平均查找长度为： 
ASL成功=1×4+2×26=1．3



图5．3哈希表的操作过程(2)


现在求查找不成功的平均查找长度(ASL不成功)，假设给定键x，它不在哈希表中，也需要按照查找过程找到空位置为止。分析哈希函数可知h(x)可能的取值为0~4。

(1) 若h(x)=0，单链表0的长度为1，探测一次确定查找失败。

(2) 若h(x)=1，单链表1的长度为2，探测两次确定查找失败。

(3) 若h(x)=2，单链表2的长度为2，探测两次确定查找失败。

(4) 若h(x)=3，单链表3的长度为1，探测一次确定查找失败。

(5) 若h(x)=4，单链表4的长度为0，探测0次确定查找失败。

对应的查找不成功的平均查找长度为： 
ASL不成功=1+2+2+1+05=1．2
一般来说，使用拉链法解决冲突的哈希表的查找性能更好，但占用的空间较多。目前，C++和Python等语言中提供的哈希表均用拉链法或者改进方法实现，查找时间可以接近O(1)。

5．1．2哈希表的知识点

在实现哈希表时其中元素的类型通常分为两种，一种是每个元素含单个键key，这样的哈希表称为哈希集合； 另一种是每个元素为键值对(key，value)，这样的哈希表称为哈希映射。通常，哈希集合用于除重、判重和快速查找，哈希映射用于计数、判重、分组数据存储和快速查找等。

1． C++中的哈希集合

C++ STL提供的哈希集合为unordered_set类模板，每个元素为一个键，所有键是唯一的。unordered_set用哈希表实现，使用拉链法解决冲突，所有元素是无序排列的，按键查找的时间复杂度接近O(1)。unordered_set的主要成员函数如下。

 empty()： 判断哈希集合是否为空。

 size()： 返回哈希集合的长度。

 ［k］： 返回哈希集合中键为k的元素。

 find(k)： 如果哈希集合中存在键为k的元素，返回其迭代器，否则返回end()。

 count(k)： 返回哈希集合中键k出现的次数，结果为0或者1。

 insert(e)： 在哈希集合中插入元素e。

 emplace(e)： 在哈希集合中插入元素e，比insert（e）的效率更高。

 erase()： 从哈希集合中删除一个或者几个元素。

 clear()： 删除哈希集合中的所有元素。

 begin()： 返回哈希集合中首元素的迭代器。

 end()： 返回哈希集合中尾元素的后一个位置的迭代器。

 C++： 





1unordered_set<int> hset;//定义元素类型为int的哈希集合

2hset.insert(3);//插入3

3hset.insert(1);//插入2

4hset.insert(2);//插入2

5printf("%d＼n",hset.count(1));//输出:1

6hset.erase(1);//删除1

7for(auto x:hset)//输出:2 3

8printf("%d ",x);

9printf("＼n");



2．  C++中的哈希映射

C++STL提供的哈希映射为unordered_map类模板，每个元素为pair类型，pair结构类型的声明如下： 





1struct pair {

2T1 first;//关键字成员

3T2 second;//值成员

4};


其中，first对应key，要求所有元素的键是唯一的，second对应值value。同时，pair对==、!=、<、>、<=、>=共6个运算符进行重载，提供了按照字典序对元素对进行大小比较的比较运算符模板函数。

unordered_map用哈希表实现，使用拉链法解决冲突，所有元素是无序排列的，按键查找的时间复杂度接近O(1)。unordered_map的主要成员函数如下。

 empty()： 判断哈希映射是否为空。

 size()： 返回哈希映射中实际的元素个数。

 map［k］： 返回键为k的元素，当其不存在时以k作为键插入一个元素。

 at［k］： 同map［k］。

 find(k)： 在哈希映射中查找键为k的元素。

 count(k)： 返回哈希映射中键为k的元素的个数，结果为1或者0。

 insert(e)： 在哈希映射中插入一个元素e并返回该元素的位置。

 emplace(e)： 在哈希映射中插入元素e，比insert(e)的效率更高。

 erase()： 删除哈希映射中的一个或者几个元素。

 clear()： 删除哈希映射中的所有元素。

 begin()： 返回哈希映射中首元素的迭代器。

 end()： 返回哈希映射中尾元素的后一个位置的迭代器。

 C++： 



1unordered_map<string,int> hmap;  //定义键为string、值为int的哈希映射

2hmap.insert(pair<string,int>("Mary",3));//插入("Mary",3) 

3hmap［"Smith"］=1;//插入("Smith",1)

4hmap.insert(make_pair<string,int>("John",2));　　//插入("John",2)

5printf("%d＼n",hmap.count("Smith"));//输出:1 

6hmap.erase("Mary");//删除Mary的元素 

7for(auto x:hmap)//输出:［John,2］ ［Smith,1］ 

8cout << "［" << x.first << ","  << x.second << "］  ";

9cout<< endl;



3．  Python中的哈希集合

在Python中提供了集合类型，用哈希表实现，在集合中存放不可变类型数据，如字符串、数字或者元组。集合是一个无序的不重复元素序列，其基本功能包括关系测试和消除重复元素。两个集合a和b之间可以做-、|、&和^运算，其中a-b返回a中包含但b中不包含的元素的集合，a | b返回a或b中包含的所有元素的集合，a & b返回a和b中都包含的元素的集合，a^b返回不同时包含于a和b的元素的集合。

使用大括号{ }或者set()函数创建集合，但创建一个空集合必须用set()而不是用{ }，因为{ }用来创建一个空字典。集合s的基本操作如下。

 len(s)： 返回集合s中元素的个数。

 x in s： 若元素x在集合s中，返回True，否则返回False。

 x not in s： 若元素x不在集合s中，返回True，否则返回False。

 s．add(x)： 向集合s中添加元素x。

 s．clear()： 移除集合s中的所有元素。

 s．isdisjoint(t)： 判断两个集合s和t是否不存在交集，若不存在返回True，否则返回False。

 s．issubs(t)： 判断集合s是否为集合t的子集。

 s．remove(x)： 移除集合s中的元素x，如果元素x不存在，则会发生错误。

 s．discard(x)： 移除集合s中的元素x，如果元素x不存在，不会发生错误。

 s．update(x)： 将x添加到集合s中，且参数可以是列表、元组或者字典等。

 s．difference(t)： 返回两个集合s和t的差集，即s-t。

 s．intersection(t)： 返回两个集合s和t的交集，即s & t。

 s．union(t)： 返回两个集合s和t的并集，即s | t。

 s．symmetric_difference(t)： 返回除集合s和集合t共有的元素以外的元素，即s^t。

 Python： 



1hset=set()#定义元素类型为int的哈希集合

2hset.add(3)#插入3

3hset.add(1)#插入2

4hset.add(2)#插入2

5print(1 in hset)#输出:True

6hset.remove(1)#删除1

7for x in hset:#输出:2 3

8print(x,end=' ')

9print()



4．  Python中的哈希映射

Python中提供的字典类型相当于哈希映射，也是用哈希表实现。字典可以存储任意类型的对象，每个元素由key: value构成，其中key是键，value是对应的值，中间用逗号分隔，整个字典包含在大括号({ })中，键必须是唯一的，但值不必唯一。值可以取任何数据类型，但键必须是不可变的数据类型，如字符串、数字或者元组。

使用大括号{ }或者dict()函数创建字典。字典dict的基本操作如下。

 len(dict)： 返回字典dict中元素的个数。

 dict［key］： 返回字典dict中键key的值。

 dict．clear()： 移除字典dict中的所有元素。

 key in dict： 如果键key在字典dict中，返回True，否则返回False。

 keynot in dict： 如果键key不在字典dict中，返回True，否则返回False。

 dict．has_key(key)： 如果键key在字典dict中，返回True，否则返回False。

 dict．items()： 以列表形式返回字典dict中可遍历的(键，值)元组数组。

 dict．keys()： 以列表形式返回字典dict中的所有键。

 dict．values()： 以列表形式返回字典dict中的所有值。

 dict．get(key, default=None)： 返回字典dict中指定键的值，如果值不在字典中，则返回default值。

 dict．setdefault(key，default=None)： 和get()类似，但如果键不在字典中，将会添加键，并将值设置为default。

 pop(key［,default］)： 删除字典dict中键key对应的值，返回值为被删除的值。key值必须给出，否则将返回default值。

 popitem()： 随机返回并删除字典dict中的最后一对键值。

 Python： 



1hmap=dict()#定义一个哈希字典

2hmap［"Mary"］=3   #插入("Mary",3) 

3hmap［"Smith"］=1#插入("Smith",1)

4hmap［"John"］=2#插入("John",2)

5print("Smith" in hmap)#输出:True

6del hmap［"Mary"］ #删除Mary的元素 

7for name,v in hmap.items():#输出:［Smith,1］ ［John,2］

8print("［%s,%d］"%(name,v),end=' ')

9print()



另外，Python提供了字典dict的一个子类defaultdict，用defaultdict函数创建该子类的对象。以下语句定义一个defaultdict类对象dict1： 



dict1=defaultdict(factory_function)


其中，factory_function可以是list、set、str等，作用是当key不存在时返回工厂函数的默认值，如list对应［ ］、str对应空字符串、set对应set()、int对应0，也就是说dict1会为一个不存在的键提供默认值，从而避免KeyError异常。dict1的其他功能与dict相同。

5.2哈希表的实现
5．2．1LeetCode705——设计哈希集合★

【问题描述】不使用任何内建的哈希表库设计一个哈希集合，实现MyHashSet类。

(1) void add(key)： 向哈希集合中插入值key。

(2) bool contains(key)： 返回哈希集合中是否存在这个值key。

(3) void remove(key)： 将给定值key从哈希集合中删除，如果其中没有这个值，什么也不做。

示例： 





MyHashSet myHashSet = new MyHashSet();

myHashSet.add(1);//set=［1］

myHashSet.add(2); //set=［1, 2］

myHashSet.contains(1); //返回true

myHashSet.contains(3); //返回false(未找到)

myHashSet.add(2); //set=［1, 2］

myHashSet.contains(2); //返回true

myHashSet.remove(2); //set=［1］

myHashSet.contains(2); //返回false(已移除)



【限制】0≤key≤106，最多调用104次add、remove和contains。

【解题思路】开放定址法(线性探测法)。相关原理参见5．1．1节，这里最多调用104次add、remove和contains，所以设置哈希集合的长度为MAXH=10 000，设置哈希函数为h(k)=k%P，P=9997，用NULLKEY=-1表示空位置键，DELKEY=-2表示已删除位置的键。

(1) add(key)： 求出d=key%P，若ht［d］=d或者ht［d］为空位置，或者ht［d］为已删除位置，在ht［d］插入key(ht［d］=d时插入key保证哈希表中的键唯一)，否则说明有冲突，使用线性探测法，即置d=(d+1)%MAXH，再进行试探。

 C++： 





1void add(int key) { //插入key

2int d=key%P;//求d0

3while(ht［d］!=key && ht［d］!=NULLKEY && ht［d］!=DELKEY) {

4d=(d+1)%MAXH;//找到NULLKEY、DELKEY的位置d

5}

6ht［d］=key;

7}



(2) contains(key)： 求出d=key%P，若ht［d］=d(查找成功)或者ht［d］为空位置(查找失败)，结束查找，否则使用线性探测法，即置d=(d+1)%MAXH，再进行试探。对于找到的d，若该位置为NULLKEY，说明查找失败，即哈希表中不包含key，返回false； 若该位置不为NULLKEY(因为key≥0，该位置不可能为DELKEY)，说明哈希表中包含key，返回true。

 C++： 





1bool contains(int key) {//是否包含key

2return ht［hash(key)］!=NULLKEY;

3}



(3) remove(key)： 按照contains(key)的查找过程找到key的位置d，若该位置不是NULLKEY，则置为DELKEY，否则不修改。

 C++： 



1void remove(int key) {//删除key

2int d=hash(key);

3if(ht［d］!=NULLKEY)

4ht［d］=DELKEY; 

5}




扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode705-1．docx】
Q： 上述题目中约定0≤key≤106，初学者Chen直接用一个长度为106+1的布尔数组ht作为哈希表，先初始化所有元素为false，当插入key时置ht［key］=true，请问Chen的实现和上述实现相比有什么优缺点？

A： Chen的实现算法简单，不需要解决冲突，所以速度更快，查找、插入和删除算法的时间复杂度均为O(1)，但占用的空间较多，并不能体现哈希表的本质。哈希表是将一个大数据范围映射为一个较小的数据范围，必须解决冲突问题。



5．2．2LeetCode706——设计哈希映射★

【问题描述】不使用任何内建的哈希表库设计一个哈希映射，实现MyHashMap类。

(1) MyHashMap()： 用空映射初始化对象。

(2) void put(int key，int value)： 求出d=key%MAXH，向HashMap插入一个键值对(key，value)，如果key已经存在于映射中，则更新其对应的值value。

(3) int get(int key)： 返回特定的key所映射的value，如果映射中不包含key的映射，返回-1。

(4) void remove(int key)： 如果映射中存在key的映射，则移除key和它所对应的value。

示例： 



MyHashMap myHashMap=new MyHashMap();

myHashMap.put(1, 1);//myHashMap现在为［［1,1］］

myHashMap.put(2, 2); //myHashMap现在为［［1,1］, ［2,2］］

myHashMap.get(1);//返回1，myHashMap现在为［［1,1］, ［2,2］］

myHashMap.get(3);//返回-1(未找到)，myHashMap现在为［［1,1］, ［2,2］］

myHashMap.put(2, 1); //myHashMap现在为［［1,1］, ［2,1］］(更新已有的值)

myHashMap.get(2);//返回1，myHashMap现在为［［1,1］, ［2,1］］

myHashMap.remove(2); //删除键为2的数据，myHashMap现在为［［1,1］］

myHashMap.get(2);//返回-1(未找到)，myHashMap现在为［［1,1］］



【限制】0≤key≤106，最多调用104次put、get和remove。

【解题思路】拉链法。相关原理参见5．1．1节，设计哈希函数为h(k)=k%MAXH，置MAXH=997。在哈希表的结点类型SNode中包含关键字key、值val和指向下一个结点的指针next。哈希表数组为ht［0．．MAXH-1］，其中ht［i］存放指向单链表i的首结点(单链表i由哈希地址为i的结点组成)。

(1) MyHashMap()： 将ht的所有元素初始化为NULL。

(2) put(key，value)： 求出d=key%P，在单链表d中查找key的结点，若找到了这样的结点p，置结点p的值为value，否则新建结点q存放<key，value>，将其插入单链表d的头部。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode706．docx】
(3) get(key)： 求出d=key%P，在单链表d中查找key的结点，若找到了这样的结点p，返回结点p的值，否则返回-1。

(4) remove(key)： 求出d=key%P，在单链表d中查找key的结点，若找到了这样的结点p，通过前驱结点pre删除结点p，否则不修改。

说明： 5.2.1节的LeetCode705使用开放定址法实现，也可以使用拉链法实现。同样，5.2.2节的LeetCode706使用拉链法实现，也可以使用开放定址法实现。

5．3哈希集合应用的算法设计
5．3．1LeetCode349——两个数组的交集★

问题描述参见第1章中的1．3．6节。

【解题思路】用哈希集合实现除重。由于输出结果中的每个元素一定是唯一的，所以先用hset1对nums1除重，用hset2对nums2除重，再对hset1和hset2求交集ans。对应的算法如下。

 C++： 



1class Solution {

2public:

3vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

4unordered_set<int> hset1,hset2;

5for(int x:nums1) hset1.insert(x);

6for(int y:nums2) hset2.insert(y);

7return intersection(hset1,hset2);

8}

9vector<int> intersection(unordered_set<int>&hset1,unordered_set<int>&hset2) {

10if(hset1.size()>hset2.size()) {

11return intersection(hset2,hset1);

12}

13vector<int> ans;

14for(int x:hset1) {//求交集ans

15if(hset2.count(x)) ans.push_back(x);

16}

17return ans;

18}

19};



提交运行： 



结果：通过;时间：12ms;空间：10.5MB



 Python： 



1class Solution:

2def intersection(self, nums1: List［int］, nums2: List［int］) > List［int］:

3hset1=set(nums1)

4hset2=set(nums2)

5return list(hset1 & hset2)



提交运行： 



结果：通过;时间：24ms;空间：15.1MB



5．3．2LeetCode202——快乐数★

【问题描述】编写一个算法来判断一个数n是否为快乐数。对于一个正整数，每一次将该数替换为其每个位置上的数字的平方和，然后重复这个过程，直到这个数变为1，也可能是无限循环，但始终变不到1。如果这个过程的结果为1，那么这个数就是快乐数。如果n是快乐数，则返回 true，否则返回false。

例如，n=19，12+92=82，82+22=68，62+82=100，12+02+02=1，返回true。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode202．docx】
【限制】1≤n≤231-1。

【解题思路】用哈希集合实现除重。对于n，按题目要求产生一个整数序列，当遇到1时表示n为快乐数。但是这个序列中可能出现相同的整数，如果这样，一定会陷入死循环，例如n=1，12=1就是如此，所以需要除重，这里用哈希集合hset实现除重，也就是当hset中不包含n时才将n插入hset中。

5．3．3LeetCode217——存在重复元素★

【问题描述】给定一个整数数组nums，如果任一数值在数组中至少出现两次，返回 true； 如果数组中的每个元素互不相同，返回 false。

例如，nums=［1，2，3，1］，答案为true； nums=［1，2，3，4］，答案为false。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode217．docx】
【限制】1≤nums．length≤105，-109≤nums［i］≤109。

【解题思路】用哈希集合实现判重。题目就是判断nums中是否存在重复的元素，若存在，返回true，否则返回false。这里用哈希集合hset实现判重，也就是用x遍历nums，若x在hset中，返回true，否则将x插入hset中。最后返回false。

5．3．4LeetCode379——电话目录管理系统★★

【问题描述】设计一个电话目录管理系统，让它支持以下功能。

(1) PhoneDirectory(n)： 初始化0~n-1的n个电话号码。

(2) get()： 给用户分配一个未被使用的电话号码，若获取失败返回-1。

(3) check(number)： 检查电话号码number是否被使用。

(4) release(number)： 释放电话号码number，使其能够重新被分配。

示例： 



PhoneDirectory directory=new PhoneDirectory(3);

//初始化电话目录，它包括3个电话号码，即0、1和2

directory.get();

//可以返回任意未被分配的号码，这里假设返回0

directory.get();

//假设函数返回1

directory.check(2);

//号码2未被分配，所以返回true

directory.get();

//返回2，分配后只剩下一个号码未被分配





directory.check(2);

//此时号码2已经被分配，所以返回false

directory.release(2);

//释放号码2，将该号码变回未被分配状态

directory.check(2);

//号码2现在是未被分配状态，所以返回true



【限制】1≤maxNumbers≤104，0≤number<maxNumbers，调用方法的总数在［0，20000］范围内。

【解题思路】用哈希集合实现判重。用一个队列qu存放所有未被分配的电话号码，用哈希集合hset存放已被分配的电话号码。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode379．docx】
(1) PhoneDirectory(n)： 将0~n-1的n个电话号码进队。

(2) get()： 若队列不为空，出队一个电话号码x，并将其插入hset中，返回x； 否则说明没有未被分配的电话号码，返回-1。

(3) check(number)： 判断number是否在hmap中。

(4) release(number)： 从hset中删除number，将其进队。

5．3．5LeetCode128——最长连续序列★★

【问题描述】给定一个未排序的整数数组nums，找出数字连续的最长序列(不要求序列的元素在原数组中连续)的长度，设计并实现时间复杂度为O(n)的算法解决此问题。

例如，nums=［100，4，200，1，3，2］，其中数字连续的最长序列是［1，2，3，4］，它的长度为4，答案为4。

【限制】0≤nums．length≤105，-109≤nums［i］≤109。

【解题思路】用哈希集合实现快速查找。用ans存放答案(初始为0)。对于nums中的整数x，将x-1称为x的连续前驱，x+1称为x的连续后继，如果在nums中每个整数向后查找最大连续后继的个数，将最大值存放在ans中，最后返回ans，这样的穷举算法的时间复杂度为O(n2)。

如果x存在最大连续整数序列x，x+1，…，y，则其连续序列的长度为y-x+1，实际上从x+1到y求出的连续序列的长度一定小于y-x+1，所以仅求x(即不存在连续前驱)的连续序列的长度即可。另外，要去掉重复的整数，并且需要快速判断其中是否存在某个整数，为此用哈希集合hset实现。先置ans=0，求解过程如下： 

(1) 将nums数组中的全部整数存放到哈希集合hset中。

(2) 用x遍历hset，若x没有连续前驱，则求出其最长的连续后继，对应的连续序列的长度为y-x+1，将最大值存放到ans中。

最后返回ans。

例如，nums=［100，4，200，1，3，2，1，3，4］，将全部整数插入hset中，除重后hset=［3，2，200，4，1，100］，ans=0，用x遍历hset。

(1) x=3，存在2，即x存在连续前驱，跳过。

(2) x=2，hset中存在1，即x存在连续前驱，跳过。

(3) x=200，hset中不存在199，置y=200，在hset中查找y的最多连续后继，最终结果y=200，ans=max(0，y-x+1)=1。

(4) x=4，hset中存在3，即x存在连续前驱，跳过。

(5) x=1，hset中不存在0，置y=1，在hset中查找y的最多连续后继，依次为y=2，y=3，y=4，最终结果y=4，ans=max(0，y-x+1)=4。

(6) x=100，hset中不存在99，置y=100，在hset中查找y的最多连续后继，最终结果y=100，ans=max(4，y-x+1)=4。

hset遍历后的答案为ans=4。对应的算法如下。

 C++： 





1class Solution {

2public:

3int longestConsecutive(vector<int>& nums) {

4unordered_set<int> hset;

5for(int x:nums) hset.insert(x);//将全部整数存放到hset中

6int ans=0;//存放答案

7for(int x:hset) {

8if(hset.find(x-1)==hset.end()) {//若x不存在连续前驱

9int y=x;//以x为起点向后枚举

10while(hset.find(y+1)!=hset.end()) y++;

11ans=max(ans,y-x+1);//求最大长度

12}

13}

14return ans;

15}

16};



提交运行： 



结果：通过;时间：96ms;空间：48.5MB



上述算法尽管包含两重循环，但时间复杂度并不是O(n2)，实际上，第7行~第13行循环的执行次数最多为2n(例如，nums=［1，2，…，n］，遇到x=1时第10行的while循环执行n次，而x为其他时仅执行一次，结果ans=n)，所以算法的时间复杂度为O(n)。

 Python： 





1class Solution:

2def longestConsecutive(self, nums: List［int］) > int:

3hset=set(nums)#将全部整数存放到hset中

4ans=0#存放答案

5for x in hset:

6if x-1 not in hset:#若x不存在连续前驱

7y=x#以x为起点向后枚举

8while y+1 in hset: y+=1

9ans=max(ans,y-x+1)#求最大长度

10return ans



提交运行： 



结果：通过;时间：72ms;空间：30.5MB



5．3．6LeetCode41——缺失的第一个正数★★★

【问题描述】给定一个未排序的整数数组nums，找出其中没有出现的最小的正整数，请实现时间复杂度为O(n)并且只使用常数级别额外空间的解决方案。

例如，nums=［3，4，-1，1］，答案为2； nums=［7，8，9，11，12］，答案为1。

【限制】1≤nums．length≤5×105，-231≤nums［i］≤231-1。

【解法1】用哈希集合实现快速查找。将nums中的所有整数插入哈希集合hset中，ans从1到n+1查找，因为缺失的正数从1开始，并且最大为n+1(此时nums中不包含1~n的任何数)，如果ans包含在hset中，递增ans继续查找，否则说明ans就是缺失的第一个正数，返回ans即可。对应的算法如下。

 C++： 



1class Solution {

2public:

3int firstMissingPositive(vector<int>& nums) {

4unordered_set<int> hset;

5for(int x:nums) hset.insert(x);

6int ans=1;

7while(ans<=nums.size()+1) {

8if(hset.find(ans)==hset.end()) break;

9ans++;

10}

11return ans;

12}

13};



提交运行： 



结果：通过;时间：64ms;空间：45.4MB



 Python： 



1class Solution:

2def firstMissingPositive(self, nums: List［int］) > int:

3hset=set()

4for x in nums: hset.add(x)

5ans=1

6while ans<=len(nums)+1:

7if ans not in hset: break;

8ans+=1

9return ans



提交运行： 



结果：通过;时间：80ms;空间：28.5MB



【解法2】元素归位法。解法1的思路虽然简单，但是不符合空间复杂度为O(1)的要求，改进算法的步骤如下： 

(1) 若nums［i］=i+1(0≤i≤n-1)，则nums［i］称为归位元素，归位元素的取值范围是1~n。将所有能够归位且尚未归位的元素nums［i］(1≤nums［i］≤n且nums［i］≠nums［nums［i］-1］)通过交换操作(交换nums［i］和nums［nums［i］-1］)变为归位元素(nums［i］放在nums［nums［i］-1］中)，忽略其他元素。

(2) 从i=0开始查找没有归位元素的位置，即满足nums［i］≠i+1，则i+1就是缺失的第一个正数，若没有找到这样的i，则缺失的第一个正数为n+1。

例如，nums=［3，4，-1，1］，n=4，归位元素的取值范围是1~4，求解过程如下。

(1) nums［0］=3，3是归位元素(其归位位置应该是nums［3-1=2］)且尚未归位，交换nums［0］和nums［2］，nums=［-1，4，3，1］，此时nums［0］=-1，不是归位元素。

(2) nums［1］=4，4是归位元素且尚未归位，交换nums［1］和nums［4-1=3］，nums=［-1，1，3，4］。nums［1］=1，1是归位元素且尚未归位，交换nums［1］和nums［1-1=0］，nums=［1，-1，3，4］。此时nums［1］=-1，不是归位元素。

(3) nums［2］=3，3是已归位元素。

(4) nums［3］=4，4是已归位元素。

最后的归位结果如图5．4所示，nums［0］是归位元素，nums［1］是没有归位的元素，则答案为2。



图5．4nums的归位结果


对应的算法如下。

 C++： 



1class Solution {

2public:

3int firstMissingPositive(vector<int>& nums) {

4int n=nums.size();

5for(int i=0;i<n;i++) {

6while(nums［i］>=1 && nums［i］<=n && nums［nums［i］-1］!=nums［i］) {

7swap(nums［i］,nums［nums［i］-1］);

8}

9}

10for(int i=0;i<n;i++) {

11if(nums［i］!=i+1) return i+1;

12}

13return n+1;

14}

15};



提交运行： 



结果：通过;时间：40ms;空间：30.5MB



 Python： 



1class Solution:

2def firstMissingPositive(self, nums: List［int］) > int:

3n=len(nums)

4for i in range(0,n):

5while nums［i］>=1 and nums［i］<=n and nums［nums［i］-1］!=nums［i］:

6self.swap(nums,i,nums［i］-1)

7for i in range(0,n):

8if nums［i］!=i+1: return i+1

9return n+1


10def swap(self,nums,i,j):#交换nums［i］和nums［j］

11nums［i］,nums［j］=nums［j］,nums［i］



提交运行： 



结果：通过;时间：104ms;空间：24.3MB



5．3．7LeetCode1436——旅行终点站★

【问题描述】给定一份旅游路线图，该路线图中的旅行路线用数组paths表示，其中 paths［i］=［cityAi，cityBi］，表示该路线将会从cityAi直接前往cityBi。请找出这次旅行的终点站，即没有任何可以通往其他城市的路线的城市。题目数据保证路线图会形成一条不存在循环的路线，因此恰有一个旅行终点站。

例如，paths=［［"London"，"New York"］，［"New York"，"Lima"］，［"Lima"，"Sao Paulo"］］，从"London"出发，最后抵达终点站"Sao Paulo"，本次旅行的路线是"London"→"New York"→"Lima"→"Sao Paulo"，答案为"Sao Paulo"。

【限制】1≤paths．length≤100，paths［i］．length=2，1≤cityAi．length，cityBi．length≤10，cityAi≠cityBi，所有字符串均由大小写英文字母和空格字符组成。

【解题思路】用哈希集合实现快速查找。将所有的路线［a，b］看成二元组，由a构成全部前驱城市集合，旅行终点站一定为某个b并且它没有前驱，为此A用哈希集合hset表示。对应的算法如下。

 C++： 



1class Solution {

2public:

3string destCity(vector<vector<string>> &paths) {

4unordered_set<string> hset;

5for(auto x:paths) hset.insert(x［0］);

6for(auto x:paths) {

7if(hset.count(x［1］)==0) return x［1］;

8}

9return "";

10}

11};



提交运行： 



结果：通过;时间：12ms;空间：11.2MB



 Python： 



1class Solution:

2def destCity(self, paths: List［List［str］］) > str:

3hset=set()

4for x in paths:

5hset.add(x［0］)

6for x in paths:

7if x［1］ not in hset: return x［1］



提交运行： 



结果：通过;时间：44ms;空间：15.1MB



5．4哈希映射应用的算法设计
5．4．1LeetCode350——两个数组的交集Ⅱ★

【问题描述】给定两个整数数组nums1和nums2，请以数组形式返回两个数组的交集，返回结果中每个元素出现的次数应该与元素在两个数组中都出现的次数一致(如果出现的次数不一致，则考虑取较小值)，可以不考虑输出结果的顺序。

例如，nums1=［1，2，2，1］，nums2=［2，2］，答案为［2，2］。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode350．docx】
【限制】1≤nums1．length，nums2．length≤1000，0≤nums1［i］，nums2［i］≤1000。

【解题思路】用哈希映射实现计数。题目的关键是每个数组中可能有重复的元素，这样交集中也可能存在重复的元素。用ans存放答案(初始为空)，保证nums1的长度较小，设计一个哈希表hmap累计nums1中每个元素出现的次数。用y遍历nums2，当hmap［y］>0时说明y是交集元素，将其添加到ans中，同时递减hmap［y］； 否则说明y不是交集元素。最后返回ans即可。

5．4．2LeetCode1460——通过翻转子数组使两个数组相等★

【问题描述】给定两个长度相同的整数数组target和arr，通过翻转子数组使两个数组相等。在每一步中可以选择arr的任意非空子数组并且将它翻转，能够执行此过程任意次。如果能让arr变得与target相同，返回true，否则返回false。

例如，target=［1，2，3，4］，arr=［2，4，1，3］，可以按照以下步骤使arr变成target： 

(1) 翻转子数组［2，4，1］，arr变成［1，4，2，3］。

(2) 翻转子数组［4，2］，arr变成［1，2，4，3］。

(3) 翻转子数组［4，3］，arr 变成［1，2，3，4］。

答案为true。上述方法并不是唯一的，还存在多种将arr变成target的方法。

【限制】target．length=arr．length，1≤target．length≤1000，1≤target［i］≤1000，1≤arr［i］≤1000。

【解题思路】用哈希映射实现计数。依题意，只要target和arr两个数组的所有不同的整数序列相同并且每个整数出现的次数相同，则一定能通过翻转子数组使两个数组相等，否则不能达到目的。对应的算法如下。

 C++： 



1class Solution {

2public:

3bool canBeEqual(vector<int>& target, vector<int>& arr) {

4unordered_map<int,int> hmap;

5for(int x:target) hmap［x］++;

6for(int y:arr) {

7if(hmap［y］<0) return false;

8}

9return true;

10}

11};



提交运行： 



结果：通过;时间：8ms;空间：15.4MB



 Python： 



1class Solution:

2def canBeEqual(self, target: List［int］, arr: List［int］) > bool:

3hmap=dict()

4for x in target: #计数

5if x in hmap:hmap［x］+=1

6else: hmap［x］=1

7for y in arr:

8if y in hmap:





9if hmap［y］-1<0: return False

10else:hmap［y］-=1

11else:return False

12return True



提交运行： 



结果：通过;时间：40ms;空间：15.1MB



5．4．3LeetCode383——赎金信★

【问题描述】给定两个字符串s和t，判断s能否由t中的字符组成，如果能，返回 true，否则返回 false。t中的每个字符只能在s中使用一次。

例如，s="aa"，t="ab"，答案为false； s="aa"，t="aab"，答案为true。

【限制】1≤s．length，t．length≤105，s和t由小写英文字母组成。

【解题思路】用哈希映射实现计数。设计一个哈希映射hmap，先遍历t累计每种字母出现的次数，再遍历s递减相同字母的次数。若hmap出现值小于0的元素，则返回false，否则返回true。对应的算法如下。

 C++： 



1class Solution {

2public:

3bool canConstruct(string s,string t) {

4if(s.size()>t.size()) return false;

5unordered_map<char,int> hmap;

6for(char x:t) hmap［x］++;

7for(char y:s) hmap［y］--;

8for(auto z:hmap) {

9if(z.second<0) return false;

10}

11return true;

12}

13};



提交运行： 



结果：通过;时间：16 ms;空间：8.6MB



 Python： 



1class Solution:

2def canConstruct(self, s: str, t: str) > bool:

3if len(s)>len(t): return False

4hmap={}

5for x in t:

6if x in hmap: hmap［x］+=1

7else: hmap［x］=1

8for y in s:

9if y in hmap:hmap［y］-=1

10else:return False#s中的字符y在t中没有出现，返回False

11for z in hmap.keys():

12if hmap［z］<0:return False

13return True



提交运行： 



结果：通过;时间：64ms;空间：15.2MB



5．4．4LeetCode347——前k个高频元素★★

【问题描述】给定一个整数数组nums和一个整数k，请返回其中出现频率前k高的元素，可以按任意顺序返回答案。

例如，nums=［1，1，1，2，2，3］，k=2，答案为［1，2］。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode347．docx】
【限制】1≤nums．length≤105，k的取值范围是［1，数组中不相同的元素的个数］，题目数据保证答案唯一，换句话说，数组中前k个高频元素的集合是唯一的。

【解题思路】用哈希映射实现计数。设计一个哈希映射计数器hmap，遍历nums求出每个整数出现的次数。再设计一个按出现次数越小越优先的小根堆minpq，遍历hmap将前k个元素进堆，对于剩余的元素x，若x出现的次数大于堆顶元素出现的次数，则出堆一次，同时将x进堆。最后堆中的k个元素就是出现频率前k高的元素。

5．4．5LeetCode242——有效的字母异位词★

【问题描述】给定两个字符串s和t，编写一个函数来判断t是否为s的字母异位词。若s和t中每个字符出现的次数都相同，则称s和t互为字母异位词。

例如，s="anagram"，t="nagaram"，答案为true； s="rat"，t="car"，答案为false。

【限制】1≤s．length，t．length≤5×104。s和t仅包含小写字母。

【解法1】用哈希映射实现计数。设计一个哈希映射hmap，先遍历s累计每种字母出现的次数，再遍历t递减相同字母的次数。若hmap中的全部元素为0，返回true，否则返回false。对应的算法如下。

 C++： 



1class Solution {

2public:

3bool isAnagram(string s, string t) {

4if(s.size()!=t.size()) return false;

5unordered_map<char,int> hmap;

6for(char x:s) hmap［x］++;

7for(char y:t) hmap［y］--;

8for(auto z:hmap) {

9if(z.second!=0) return false;

10}

11return true;

12}

13};



提交运行： 



结果：通过;时间：4ms;空间：7.2MB



 Python： 



1class Solution:

2def isAnagram(self, s: str, t: str) > bool:

3if len(s)!=len(t): return False

4hmap={}

5for x in s:

6if x in hmap: hmap［x］+=1





7else: hmap［x］=1

8for y in t:

9if y in hmap:hmap［y］-=1

10for z in hmap.keys():

11if hmap［z］!=0:return False

12return True



提交运行： 



结果：通过;时间：52ms;空间：15.3MB



【解法2】排序判断法。若s和t互为字母异位词，则它们排序的结果一定是相同的。对应的算法如下。

 C++： 



1class Solution {

2public:

3bool isAnagram(string s, string t) {

4if(s.size()!=t.size())

5return false;

6sort(s.begin(),s.end());

7sort(t.begin(),t.end());

8return s==t;

9}

10};



提交运行： 



结果：通过;时间：12ms;空间：7.2MB



 Python： 



1class Solution:

2def isAnagram(self, s: str, t: str) > bool:

3if len(s)!=len(t): return False

4s,t=list(s),list(t)

5s.sort()

6t.sort()

7return s==t



提交运行： 



结果：通过;时间：80ms;空间：16.2MB



5．4．6LeetCode205——同构字符串★

【问题描述】给定两个字符串s和t，判断它们是否为同构字符串。如果s中的字符可以按某种映射关系替换得到t，那么这两个字符串是同构字符串。每个出现的字符都应当映射到另一个字符，并且不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

例如，s="egg"，t="add"，答案为true； s="foo"，t="bar"，答案为false。

【限制】1≤s．length≤5×104，t．length =s．length，s和t由任意有效的ASCII字符组成。

【解题思路】用哈希映射实现字符映射关系。设计两个哈希映射hmap1和hmap2，hmap1［x］=y表示s中的x字符映射到t中的y字符，hmap1［y］=x表示t中的y字符映射到s中的x字符。用i从0开始遍历，置x=s［i］，y=t［i］，若x和y均没有建立映射关系，则置hmap1［x］=y和hmap2［y］=x，建立x和y之间的双向元素关系。若x或者y已经建立映射关系但映射关系错误，返回false，否则说明映射关系正确，继续遍历。遍历位置返回true。对应的算法如下。

 C++： 





1class Solution {

2public:

3bool isIsomorphic(string s, string t) {

4if(s.size()!=t.size()) return false;

5unordered_map<char,int> hmap1;

6unordered_map<char,int> hmap2;

7for(int i=0;i<s.size();i++) {

8char x=s［i］,y=t［i］;

9if(hmap1.count(x)==0 && hmap2.count(y)==0) {

10hmap1［x］=y;

11hmap2［y］=x;

12}

13else if(hmap1.count(x)==1 && hmap1［x］!=y || hmap2.count(y)==1 

14&& hmap2［y］!=x)

15return false;//不匹配返回false

16}

17return true;

18}

19};



提交运行： 



结果：通过;时间：8ms;空间：7MB



 Python： 





1class Solution:

2def isIsomorphic(self, s: str, t: str) > bool:

3if len(s)!=len(t): return False

4hmap1,hmap2={},{}

5for i in range(0,len(s)):

6x,y=s［i］,t［i］

7if x not in hmap1 and y not in hmap2:

8hmap1［x］,hmap2［y］=y,x

9elif(x in hmap1 and hmap1［x］!=y) or (y in hmap2 and hmap2［y］!=x):

10return False#不匹配返回False

11return True



提交运行： 



结果：通过;时间：36ms;空间：15.2MB



5．4．7LeetCode1——两数之和★

【问题描述】给定一个整数数组nums和一个整数目标值target，请在该数组中找出和为目标值target的两个整数，并返回它们的数组下标。可以假设每种输入只会对应一个答案，但是数组中的同一个元素在答案中不能重复出现。可以按任意顺序返回答案。

例如，nums=［2，7，11，15］，target=9，答案为［0，1］； nums=［3，2，4］，target=6，答案为［1，2］。

【限制】2≤nums．length≤104，-109≤nums［i］≤109，-109≤target≤109，只会存在一个有效答案。


扫一扫


源程序


【看源程序代码请扫描二维码，对应的Word文件为LeetCode1．docx】
【解题思路】用哈希映射实现快速查找。设计一个哈希映射hmap，其中元素hmap［d］=i表示nums数组中整数d的序号为i。用i从0开始遍历nums，若target-nums［i］在hmap中，则两个元素target-nums［i］(其序号为hmap［target-nums［i］］)和nums［i］的和为目标值target，返回{hmap［target-nums［i］］，i}即可，否则置hmap［nums［i］］=i。

5．4．8LeetCode219——存在重复元素Ⅰ★

【问题描述】给定一个整数数组nums和一个整数k，判断数组中是否存在两个不同的索引i和j满足nums［i］=nums［j］且|i - j|≤k，如果存在，返回 true，否则返回 false。

例如，nums=［1，2，3，1］，k=3，由于nums1［0］=nums［3］，答案为true； nums=［1，2，3，1，2，3］，k=2，答案为false。

【限制】1≤nums．length≤105，-109≤nums［i］≤109，0≤k≤105。

【解题思路】用哈希映射实现快速查找。设计一个哈希映射hmap，其中元素hmap［d］=i表示nums数组中整数d的序号为i。用i从0开始遍历nums，置d=nums［i］，若d在hmap中并且满足条件i-hmap［d］≤k，返回true，否则置hmap［d］=i。遍历完毕返回false。对应的算法如下。

 C++： 



1class Solution {

2public:

3bool containsNearbyDuplicate(vector<int>& nums,int k) {

4unordered_map<int,int> hmap;

5int n=nums.size();

6for(int i=0;i<n;i++) {

7int d=nums［i］;

8if(hmap.count(d)==1 && i-hmap［d］<=k) return true;

9else hmap［d］=i;

10}

11return false;

12}

13};



提交运行： 



结果：通过;时间：128ms;空间：75.4 MB



 Python： 



1class Solution:

2def containsNearbyDuplicate(self, nums: List［int］, k: int) > bool:

3hmap={}#定义一个字典

4for i,d in enumerate(nums):

5if d in hmap and i-hmap［d］<=k:#找到后返回结果

6return True

7else:

8hmap［d］=i#添加到hmap中

9return False



提交运行： 



结果：通过;时间：68ms;空间：26.1MB



5．4．9LeetCode49——字母异位词的分组★★

【问题描述】给定一个字符串数组strs，请将字母异位词组合在一起，可以按任意顺序返回结果列表。字母异位词是通过重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

例如，strs=［"eat"，"tea"，"tan"，"ate"，"nat"，"bat"］，答案为［［"bat"］，［"nat"，"tan"］，［"ate"，"eat"，"tea"］］。

【限制】1≤strs．length≤104，0≤strs［i］．length≤100，strs［i］仅包含小写字母。



图5．5hmap中存储的数据

【解题思路】用哈希映射实现分组。从字符串角度看，显然所有字母异位词的排序结果是相同的，为此设计unordered_map<string，vector<string>>类型的哈希映射hmap，参考5．4．5节中的解法2，以排序结果为键，以字母异位词为值，通过遍历strs产生hmap，例如样例对应的hmap如图5．5所示，再遍历hmap将所有值存放到ans中，最后返回ans即可。

对应的算法如下。

 C++： 





1class Solution {

2public:

3vector<vector<string>> groupAnagrams(vector<string>& strs) {

4unordered_map<string,vector<string>> hmap;

5for(string x:strs) {

6string key=x;

7sort(key.begin(),key.end());

8hmap［key］.push_back(x);

9}

10vector<vector<string>> ans; 　　//存放答案

11for(auto x:hmap) {

12ans.push_back(x.second);

13}

14return ans;

15}

16};



提交运行： 



结果：通过;时间：36ms;空间：20.1MB



 Python： 





1class Solution:

2def groupAnagrams(self, strs: List［str］) > List［List［str］］:

3hmap=dict()

4for x in strs:

5key="".join((lambda x:(x.sort(),x)［1］)(list(x)))

6if key in hmap: hmap［key］.append(x)

7else: hmap［key］=［x］

8ans=［］#存放答案

9for v in hmap.values():

10ans.append(v)

11return ans



提交运行： 



结果：通过;时间：56ms;空间：18.1MB



5．4．10LeetCode249——移位字符串的分组★★

【问题描述】给定一个字符串，对该字符串可以进行“移位”操作，也就是将字符串中的每个字母都变为其在字母表中后续的字母，如"abc"→"bcd"，这样可以持续进行移位操作，从而生成移位序列"abc"→"bcd"→…→"xyz"。给定一个仅包含小写字母的字符串的列表strings，将该列表中所有满足移位操作规律的组合进行分组并返回。

例如，strings=［"abc"，"bcd"，"acef"，"xyz"，"az"，"ba"，"a"，"z"］，答案为［［"abc"，"bcd"，"xyz"］，［"az"，"ba"］，［"acef"］，［"a"，"z"］］。可以认为字母表首尾相接，所以'z'的后续为'a'，因此［"az"，"ba"］也满足移位操作规律。

【解题思路】用哈希映射实现分组。哈希映射hmap的设计与5．4．9节类似，其中键值为字符串的各字符转换为与第一个字符在字母表中的相对距离，将相同键值的字符串存放到对应的向量中。最后遍历hmap取出所有向量值即可。对应的算法如下。

 C++： 





1class Solution {

2public:

3vector<vector<string>> groupStrings(vector<string>& strings) {

4string key;

5unordered_map<string,vector<string>> hmap;

6for(string x:strings) {

7key="";

8for(int i=1;i<x.size();i++)

9key+=(x［i］-x［0］+26)%26;//当前字符与首字符的距离

10hmap［key］.push_back(x);

11}

12vector<vector<string>> ans;　　//存放答案

13for(auto x:hmap)

14ans.push_back(x.second);

15return ans;

16}

17};



提交运行： 



结果：通过;时间：4ms;空间：7.9MB



 Python： 





1class Solution:

2def groupStrings(self, strings: List［str］) > List［List［str］］:

3hmap=dict()

4for x in strings:

5key=""

6for i in range(1,len(x)):

7key+=chr((ord(x［i］)-ord(x［0］)+26)%26)

8#当前字符与首字符的距离

9if key in hmap: hmap［key］.append(x)

10else: hmap［key］=［x］

11ans=［］#存放答案

12for v in hmap.values():

13ans.append(v)

14return ans



提交运行： 



结果：通过;时间：44ms;空间：15.1MB



推荐练习题
1． LeetCode3——无重复字符的最长子串★★

2． LeetCode136——只出现一次的数字★

3． LeetCode137——只出现一次的数字Ⅱ★★

4． LeetCode142——环形链表Ⅱ★★

5． LeetCode160——相交链表★

6． LeetCode268——丢失的数字★

7． LeetCode287——寻找重复数★★

8． LeetCode290——单词的规律★

9． LeetCode291——单词的规律Ⅱ★★

10． LeetCode451——根据字符出现的频率排序★★

11． LeetCode454——四数相加Ⅱ★★

12． LeetCode599——两个列表的最小索引总和★

13． LeetCode771——宝石与石头★

14． LeetCode804——唯一摩尔斯密码词★

15． LeetCode895——最大频率栈★★★

16． LeetCode1429——第一个唯一数字★★

17． LeetCode1399——统计最大组的数目★

18． LeetCode2347——最好的扑克手牌★