邯郸医院网站建设,单页营销式网站模板,网站标签图片修改,网易企业邮箱怎么切换账号Python蓝桥杯训练#xff1a;基本数据结构 [哈希表] 文章目录Python蓝桥杯训练#xff1a;基本数据结构 [哈希表]一、哈希表理论基础知识1、开放寻址法2、链式法二、有关哈希表的一些常见操作三、力扣上面一些有关哈希表的题目练习1、[有效的字母异位词](https://leetcode.cn…Python蓝桥杯训练基本数据结构 [哈希表] 文章目录Python蓝桥杯训练基本数据结构 [哈希表]一、哈希表理论基础知识1、开放寻址法2、链式法二、有关哈希表的一些常见操作三、力扣上面一些有关哈希表的题目练习1、[有效的字母异位词](https://leetcode.cn/problems/valid-anagram/)2、[两个数组的交集](https://leetcode.cn/problems/intersection-of-two-arrays/)3、[快乐数](https://leetcode.cn/problems/happy-number/)4、[两数之和](https://leetcode.cn/problems/two-sum/)5、[四数相加Ⅱ](https://leetcode.cn/problems/4sum-ii/)6、[三数之和](https://leetcode.cn/problems/3sum/)7、[四数之和](https://leetcode.cn/problems/4sum/)四、如何选择哈希表实现对象本次博客我是通过Notion软件写的转md文件可能不太美观大家可以去我的博客中查看北天的 BLOG持续更新中另外这是我创建的编程学习小组频道想一起学习的朋友可以一起 一、哈希表理论基础知识
哈希表Hash table是一种常用的数据结构它通过使用哈希函数将数据元素映射到数组中的某个位置并使用链表维护元素间的映射关系。哈希表具有查询、插入、删除等操作的高效性因此被广泛应用于数据存储、查找和删除等场景。
哈希函数Hash function是哈希表的核心部分它通过一种特定的映射方式将数据元素映射到数组的某个位置上。一般来说哈希函数需要满足以下三个条件
哈希函数对于任意的数据元素都能生成一个数组下标对于不同的数据元素生成的下标尽可能不同对于相同的数据元素生成的下标始终相同。
如果哈希函数生成的下标相同我们称之为哈希冲突Hash collision。哈希冲突的处理方式有很多种常见的有开放寻址法和链式法。
1、开放寻址法
当冲突发生时在下一个空余的位置存储该数据元素。
开放寻址法的思想是当哈希冲突发生时继续寻找数组中下一个空闲的位置并将数据元素插入该位置。具体来说开放寻址法中有三种常用的冲突解决方法
线性探测Linear Probing当哈希冲突发生时以步长为1在数组中寻找下一个空闲的位置并将数据元素插入该位置。二次探测Quadratic Probing当哈希冲突发生时以步长的平方为增量在数组中寻找下一个空闲的位置并将数据元素插入该位置。双重哈希Double Hashing当哈希冲突发生时使用第二个哈希函数计算出步长并在数组中寻找下一个空闲的位置并将数据元素插入该位置。 优点
对于小规模数据集开放寻址法具有较小的空间开销开放寻址法的数据存储在数组中因此具有较好的局部性缓存命中率高。
缺点
开放寻址法对于冲突的解决方式较为固定不具有链式法灵活的处理方式随着数据集的扩大开放寻址法容易出现聚集现象即数据元素的分布不均匀从而导致探测冲突的频率增加插入和查找效率降低。
应用场景
适用于小规模数据集并且需要快速随机访问的场景。
2、链式法
链式法的思想是当哈希冲突发生时在该位置存储一个链表并将该数据元素插入链表中。链式法的实现相对简单具体来说可以使用数组和链表组合实现即数组中每个位置存储一个指向链表头节点的指针。 优点
链式法的数据存储在链表中因此对于大规模数据集可以有效地解决聚集现象具有较好的扩展性链式法的处理方式较为灵活能够处理各种类型的哈希冲突。
缺点
链式法的链表节点需要额外的空间存储指针信息因此对于空间的使用有一定的额外开销链式法的查询效率取决于链表的长度因此如果链表过长查询效率会降低。
应用场景
适用于大规模数据集并且需要支持高效插入和删除操作的场景。
开放寻址法和链式法都是哈希表解决哈希冲突的有效方法。在选择哪种方法时需要考虑数据集大小、查询、插入和删除操作的需求以及空间的限制等因素。在实际应用中常常需要根据实际情况选择适合的哈希表实现方式。
哈希表的查询、插入、删除等操作都是基于哈希函数的。查询操作是通过计算出该数据元素的哈希值并在数组中找到对应的位置如果该位置存在该数据元素则返回该数据元素。插入操作是在查询操作的基础上在数组中的对应位置插入该数据元素。删除操作是通过查询操作找到该数据元素并在数组中删除该数据元素。
总的来说哈希表是一种高效的数据存储和查询结构它通过使用哈希函数和链表维护数据元素之间的映射关系在提高数据存储和查询效率的同时也具有解决哈希冲突的能力。
二、有关哈希表的一些常见操作
Python 中的哈希表实现是通过内置的 **dict**数据类型实现的。下面是一些常见的哈希表操作及其对应的 Python 代码 插入元素 使用 **dict[key] value**进行插入如果 key 已经存在会将对应的 value 进行更新。 d {}
d[key1] value1
d[key2] value2
d[key1] new_value1 # 更新 key1 对应的值删除元素 使用 **del dict[key]**进行删除操作如果 key 不存在会抛出 KeyError 异常。 d {key1: value1, key2: value2}
del d[key1]查询元素 使用 **dict[key]**进行查询操作如果 key 不存在会抛出 KeyError 异常。 d {key1: value1, key2: value2}
value d[key1]判断元素是否存在 可以使用 **key in dict**来判断 key 是否存在于 dict 中。 d {key1: value1, key2: value2}
if key1 in d:print(key1 exists in the dictionary)遍历元素 可以使用 **for key in dict**来遍历 dict 中的所有 key也可以使用 dict.items() 方法来遍历 dict 中的所有键值对。 d {key1: value1, key2: value2}
for key in d:print(key, d[key])for key, value in d.items():print(key, value)三、力扣上面一些有关哈希表的题目练习
1、有效的字母异位词 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。 注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
示例1
输入: s anagram, t nagaram
输出: true示例2
输入: s rat, t car
输出: false提示
1 s.length, t.length 5 * 10^4
s 和 t 仅包含小写字母进阶: 如果输入字符串包含 unicode 字符怎么办你能否调整你的解法来应对这种情况 这道题目题目意思很简单实现起来也很快Python解决这个题目有很多种方法在这里我介绍三种方法。 1、字典计数将两个字符串都转化为字典然后比较这两个字典是否相等。字典中 key 为字符串中的字符value 为字符出现的次数。
2、排序对两个字符串分别进行排序然后比较两个有序字符串是否相等。
3、哈希表使用长度为 26 的数组记录每个字符出现的次数然后比较两个数组是否相等。 ✍ 方法一 class Solution: def isAnagram(self, s: str, t: str) - bool:if len(s) ! len(t):return Falsedict_s {}dict_t {}for char in s:dict_s[char] dict_s.get(char, 0) 1for char in t:dict_t[char] dict_t.get(char, 0) 1return dict_s dict_t该算法的时间复杂度为 O(n)空间复杂度为 O(n)。
方法二
class Solution: def isAnagram(self, s: str, t: str) - bool:return sorted(s) sorted(t)该算法的时间复杂度为 O(nlogn)空间复杂度为 O(n)由于排序需要使用额外的空间。
方法三
class Solution:def isAnagram(self, s: str, t: str) - bool:record [0] * 26for i in s:record[ord(i) - ord(a)] 1for i in t:record[ord(i) - ord(a)] - 1for i in range(26):if record[i] ! 0:return Falsereturn True该算法的时间复杂度为 O(n)空间复杂度为 O(1)。由于字符串中只包含小写字母因此数组的长度为 26。
B站上面卡尔老师对于这道题的解题思路是使用哈希表解决讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1YG411p7BA/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 2、两个数组的交集 给定两个数组 nums1和 nums2返回 *它们的交集*。输出结果中的每个元素一定是 **唯一**的。我们可以 **不考虑输出结果的顺序** 。 示例1
输入nums1 [1,2,2,1], nums2 [2,2]
输出[2]示例2
输入nums1 [4,9,5], nums2 [9,4,9,8,4]
输出[9,4]
解释[4,9] 也是可通过的提示
1 nums1.length, nums2.length 1000
0 nums1[i], nums2[i] 1000这道题目需要判断两个数组的交集也就是两个数组的重复项而且需要注意的是输出的结果中的每个元素一定是唯一的意思是我们需要将输出结果去重这道题我们可以采用暴力枚举法解决两层for循环然后判断就可以解决暴力时间复杂度比较高我们还可以使用哈希表进行提高效率根据题目我们知道需要计算两个数组的交集可以利用哈希表的思想遍历第一个数组将其中的元素作为 key 存入哈希表中。接着遍历第二个数组如果当前元素在哈希表中存在则将其加入结果集中最后返回结果集。 ✍ 哈希表法我们有多种写法首先我们看一下第一种详细写法 class Solution:def intersection(self, nums1, nums2):# 创建一个空的哈希表val_dict {}# 创建一个空的结果列表ans []# 遍历数组 nums1 中的元素将其作为哈希表中的键对应的值设置为 1for num in nums1:val_dict[num] 1# 遍历数组 nums2 中的元素for num in nums2:# 如果当前元素在哈希表中存在且对应的值为 1if num in val_dict.keys() and val_dict[num] 1:# 将当前元素加入结果列表 ans 中ans.append(num)# 将哈希表中对应的值设置为 0以便去重val_dict[num] 0# 返回结果列表 ansreturn ans这段代码的时间复杂度同样为 O(mn)其中 m 和 n 分别为两个数组的长度。
需要注意的是这段代码中使用了字典的 **keys()**方法来判断某个键是否存在于字典中但实际上可以直接使用 if num in val_dict:来判断某个键是否存在于字典中因为在 Python 中in 操作符默认会在字典的键中查找。另外在这段代码中将哈希表中对应的值设置为 0 是为了去重但实际上不需要这么做可以直接使用 set 数据类型来实现去重这样代码会更简洁。
下面是体现Python之美的简洁代码
class Solution:def intersection(self, nums1, nums2):nums1 set(nums1)nums2 set(nums2)return list(nums1 nums2)更简洁的写法是
class Solution:def intersection(self, nums1, nums2):return list(set(nums1) set(nums2))如果我们使用暴力枚举法的话我们可以枚举数组 **nums1**和 **nums2**中的每个元素判断它们是否相等如果相等就加入结果集中。具体实现代码如下
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) - List[int]:ans []for num1 in nums1:for num2 in nums2:if num1 num2 and num1 not in ans:ans.append(num1)return ans这段代码的时间复杂度为 O(mn)其中 m 和 n 分别为两个数组的长度。由于需要对结果集去重因此还需要额外的时间复杂度所以使用暴力解法不如使用哈希表或 set 数据类型来实现高效。
B站上面卡尔老师对于这道题的解题思路是使用第一种详细的哈希表法解决讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1ba411S7wu/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 3、快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
示例1
输入n 19
输出true
解释
12 92 82
82 22 68
62 82 100
12 02 02 1示例2
输入n 2
输出false提示
1 n 231 - 1这道题需要我们判断一个数是否是快乐数即根据题目定义进行一系列计算如果最终计算结果为 1那么这个数就是快乐数否则就不是快乐数。我们可以使用哈希表法来解决这个问题。 哈希表法的基本思路是对于一个数字 n我们按照题目要求进行一系列计算得到一个新的数字 m然后将 m 保存在哈希表中。如果计算后得到的数字 m 已经在哈希表中出现过了那么说明我们已经进入了一个循环这个数不是快乐数。否则我们继续按照题目要求进行计算直到得到 1 或者进入循环。
这道题同样可以使用暴力枚举法解决我们需要不断地按照题目要求计算直到得到 1 或者进入循环。具体来说我们可以编写一个计算平方和的函数 squareSum然后在一个 while 循环中不断调用这个函数直到得到 1 或者进入循环。在每一轮计算中我们将当前数字赋值给 n然后调用 squareSum 计算出一个新的数字 m。如果 m 等于 1说明这个数是快乐数否则我们继续按照题目要求计算直到得到 1 或者进入循环。 ✍ 我们使用哈希表法解决的代码如下 class Solution:def isHappy(self, n):seen set() # 用来保存已经出现过的数字while n ! 1 and n not in seen:seen.add(n)n sum(int(i) ** 2 for i in str(n))return n 1在上面代码中我们首先定义了一个空的集合 seen用来保存已经出现过的数字。然后我们使用一个 while 循环来按照题目要求进行计算直到得到 1 或者进入循环。在每一轮计算中我们首先将当前数字 n 加入到 seen 中然后按照题目要求计算出一个新的数字 m并将 m 赋值给 n。如果 n 已经出现在 seen 中了那么说明我们进入了一个循环可以直接退出循环。最后我们判断 n 是否等于 1如果是返回 True否则返回 False。
我们还可以换一种实现思路但还是使用的哈希表法那就是使用哈希表来记录出现过的数字每次计算平方和后判断是否出现过如果出现过则说明出现了循环否则继续计算。具体来说代码定义了一个函数 calculate_happy用来计算一个数每个位置上的数字的平方和。然后使用一个 **set**类型的哈希表 **record**来记录已经出现过的数字初始时 **record**是空的。接下来我们进入一个 while 循环不断计算 **n**的平方和并更新 **n**的值直到 **n**等于 1 或者 **n**在 **record**中出现过。在每一轮循环中我们首先调用 **calculate_happy**计算出 **n**的平和然后判断平方和是否等于 1如果是说明这个数是快乐数可以直接返回 True。如果平方和在 **record**中出现过说明我们已经进入了一个循环可以直接返回 False。否则将平方和加入到 **record**中并将 **n**赋值为平方和继续循环。
具体实现代码如下
class Solution:def isHappy(self, n):# 定义一个函数用来计算一个数每个位置上的数字的平方和def calculate_happy(num):sum_ 0while num:sum_ (num % 10) ** 2num num // 10return sum_# 定义一个 set 类型的哈希表 record用来记录已经出现过的数字record set()# 进入一个 while 循环不断计算 n 的平方和并更新 n 的值直到 n 等于 1 或者 n 在 record 中出现过while True:# 计算 n 的平方和n calculate_happy(n)# 如果 n 等于 1说明这个数是快乐数可以直接返回 Trueif n 1:return True# 如果平方和在 record 中出现过说明我们已经进入了一个循环可以直接返回 Falseif n in record:return False# 否则将平方和加入到 record 中并将 n 赋值为平方和继续循环else:record.add(n)如果我们使用暴力枚举法解决的话具体实现思路是我们需要不断地按照题目要求计算直到得到 1 或者进入循环。具体来说我们可以编写一个计算平方和的函数 squareSum然后在一个 while 循环中不断调用这个函数直到得到 1 或者进入循环。在每一轮计算中我们将当前数字赋值给 n然后调用 squareSum 计算出一个新的数字 m。如果 m 等于 1说明这个数是快乐数否则我们继续按照题目要求计算直到得到 1 或者进入循环。
def squareSum(n: int) - int:计算一个数每个位置上的数字的平方和res 0while n 0:digit n % 10res digit * digitn // 10return resdef isHappy(n: int) - bool:seen set() # 用来保存已经出现过的数字while n ! 1 and n not in seen:seen.add(n)n squareSum(n)return n 1在上面代码中我们首先定义了一个计算平方和的函数 squareSum这个函数会计算一个数每个位置上的数字的平方和。然后我们使用一个 while 循环来按照题目要求进行计算直到得到 1 或者进入循环。在每一轮计算中我们首先将当前数字 n 加入到 seen 中然后调用 squareSum 计算出一个新的数字 m并将 m 赋值给 n。如果 n 已经出现在 seen 中了那么说明我们进入了一个循环可以直接退出循环。最后我们判断 n 是否等于 1如果是返回 True否则返回 False。
使用暴力枚举法虽然简单但是时间复杂度较高无法通过力扣的所有测试用例。因此我们更推荐使用哈希表法来解决这个问题。 4、两数之和 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出和为目标值 target 的那两个整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例1
输入nums [2,7,11,15], target 9
输出[0,1]
解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例2
输入nums [3,2,4], target 6
输出[1,2]示例3
输入nums [3,3], target 6
输出[0,1]提示
2 nums.length 104
-109 nums[i] 109
-109 target 109
只会存在一个有效答案**进阶**你可以想出一个时间复杂度小于 O(n2)的算法吗 这道题是力扣上面的第一题是梦开始的地方也是梦醒的地方当初第一次做这个题目的时候就被难住了这是当初做这道题专门写的博客****[Python算法练习之解决两数之和问题](https://blog.csdn.net/qq_52417436/article/details/124597734)****当时信心满满的准备开始刷算法题结果就摆烂了现在我们再来看这道题目。这道题使用暴力枚举法很快就解决了我们重点还是学习一下使用哈希表法解决具体的思路就是 定义一个哈希表 hash_map用来记录每个数的下标。遍历数组 nums对于每个数 num计算出需要的另一个数 target - num并在哈希表中查找是否存在这个数。如果存在则直接返回这两个数的下标。如果不存在则将当前数的下标和值加入哈希表中继续遍历数组。 ✍ 利用哈希表解决的代码如下 class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:# 定义一个哈希表用来记录每个数的下标hash_map {}# 遍历数组 nums对于每个数 num计算出需要的另一个数 target - num并在哈希表中查找是否存在这个数for i, num in enumerate(nums):complement target - numif complement in hash_map:# 如果存在则直接返回这两个数的下标return [hash_map[complement], i]else:# 如果不存在则将当前数的下标和值加入哈希表中继续遍历数组hash_map[num] i# 如果遍历完数组都没有找到满足条件的数说明输入数据有误返回空列表return []在解决这个问题时我们首先要考虑如何遍历数组并对于每个数计算出需要的另一个数。然后我们可以使用哈希表来记录每个数的下标这样在查找另一个数时可以快速地定位。最后我们需要考虑一些特殊情况比如输入数据为空或者没有满足条件的数。
如果我们使用暴力枚举法解决的话我们需要对于每个数依次遍历剩下的数查找是否存在满足条件的数。
具体思路如下
遍历数组 nums对于每个数 num1依次遍历剩下的数 num2。如果找到两个数的和等于目标值 target则返回它们的下标。如果遍历完整个数组都没有找到满足条件的数说明输入数据有误返回空列表。
具体实现代码是
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:# 遍历数组 nums对于每个数 num1依次遍历剩下的数 num2for i, num1 in enumerate(nums):for j, num2 in enumerate(nums[i1:]):j i 1 # 由于 j 是相对于 i 的偏移量所以需要加上 i1# 如果找到两个数的和等于目标值 target返回它们的下标if num1 num2 target:return [i, j]# 如果遍历完整个数组都没有找到满足条件的数说明输入数据有误返回空列表return []需要注意的是在这个算法中我们需要对于每个数依次遍历剩下的数时间复杂度为 O(n2)O(n^2)O(n2)其中 nnn 是数组的长度。因此如果输入数据很大这个算法可能会超时。而使用哈希表的方法可以将时间复杂度降低到 O(n)O(n)O(n)。
B站上面卡尔老师对于这道题的解题思路是使用第一种详细的哈希表法解决讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1aT41177mK/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 5、四数相加Ⅱ 给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足 0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
示例1
输入nums1 [1,2], nums2 [-2,-1], nums3 [-1,2], nums4 [0,2]
输出2
解释
两个元组如下
1. (0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0
2. (1, 1, 0, 0) - nums1[1] nums2[1] nums3[0] nums4[0] 2 (-1) (-1) 0 0示例2
输入nums1 [0], nums2 [0], nums3 [0], nums4 [0]
输出1提示
n nums1.length
n nums2.length
n nums3.length
n nums4.length
1 n 200
-228 nums1[i], nums2[i], nums3[i], nums4[i] 228这道题目给了我们四个整数数组我们可以将其两两分配例如1. 遍历数组 nums1 和 nums2计算它们的和并将和存储到一个哈希表中其中哈希表的键是和的值哈希表的值是和出现的次数。再遍历数组 nums3 和 nums4计算它们的和的相反数查找哈希表中是否存在一个键等于相反数的值。如果存在将对应的值加入计数器中。遍历完数组 nums3 和 nums4 后计数器的值就是满足条件的元组个数。 除了上述方法之外我们还可以使用Python 内置的 **defaultdict来解决这个问defaultdic**是一个类似于字典dictionary的容器类型它是 Python 标准库 collections 中的一种数据类型支持所有字典所支持的操作但是在键不存在时返回一个默认值可以自己设定而不是抛出 KeyError 异常。
这道题不推荐使用暴力因为这样时间复杂度很高是通过不了的。 ✍ 使用哈希表法实现的代码如下 class Solution:def fourSumCount(self, nums1, nums2, nums3, nums4):dict {}for i in nums1:for j in nums2:if ij in dict:dict[ij] 1else:dict[ij] 1count 0for i in nums3:for j in nums4:if -(ij) in dict:count dict[-(ij)]return count时间复杂度为 O(n2)O(n^2)O(n2)其中 nnn 是数组的长度。虽然使用了哈希表来优化查找过程但仍然需要对数组进行遍历。如果输入数据很大这个算法可能会超时。
使用Python内置函数解决
from collections import defaultdictclass Solution:def fourSumCount(self, nums1, nums2, nums3, nums4):count_dict defaultdict(int)for i in nums1:for j in nums2:count_dict[i j] 1count 0for i in nums3:for j in nums4:count count_dict[-(i j)]return count上述代码具体实现步骤如下
使用 defaultdict(int) 来创建一个默认值为 0 的字典 count_dict用于存储 nums1 和 nums2 中元素的和出现的次数。遍历 nums1 和 nums2将它们的和作为字典 count_dict 的键值加 1。遍历 nums3 和 nums4计算它们的和的相反数并在字典 count_dict 中查找对应的值将值累加到计数器 count 中。返回计数器 count 的值。
这种实现方式也是时间复杂度为 O(n2)O(n^2)O(n2) 的其中 nnn 是数组的长度。
B站上面卡尔老师对于这道题的解题思路是使用第一种哈希表法解决讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1Md4y1Q7Yh/?spm_id_from333.1007.top_right_bar_window_history.content.clickvd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 6、三数之和
✍ 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。示例2
输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。示例3
输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。提示
3 nums.length 3000
-105 nums[i] 105这道题相比于两数之和虽然只是需要多找一个数但是难度却大了不少是一个比较经典的问题也是一道较为基础的数组题目。这个题目的要求是给定一个包含 n 个整数的数组 nums判断数组中是否存在三个元素 a、b、c使得 a b c 0。如果存在这样的三个元素则需要将它们所有可能的唯一组合找出来并且组合不能重复。 首先我们来思考分析题目问题有哪些解决方法大概就是下面这几种
首先可以考虑暴力解法。暴力解法的思路是枚举所有的三元组时间复杂度为 O(n3)O(n^3)O(n3)不太可取。考虑优化暴力解法。可以使用双指针的方法将时间复杂度降为 O(n2)O(n^2)O(n2)。进一步优化。可以先对数组进行排序然后再使用双指针的方法时间复杂度为 O(n2)O(n^2)O(n2)空间复杂度为 O(logn)O(log n)O(logn)。可以使用哈希表的方法时间复杂度为 O(n2)O(n^2)O(n2)空间复杂度为 O(n)O(n)O(n)。
由我们的分析可以看出来最优解法为第三种方法即先对数组进行排序再使用双指针的方法。
使用双指针的思路大致为
对 nums 数组进行排序排序后从小到大依次枚举每个数作为 a同时设定两个指针 l 和 r 分别指向 a 的后面和数组末尾即 l a 1r n - 1。在 l 和 r 的指针范围内判断 b c 的值与 -a 的大小关系如果 b c -a则将指针 r 向左移动如果 b c -a则将指针 l 向右移动如果 b c -a则找到了一组解将其加入结果列表中。对于每个枚举到的数 a如果它和它前面的数相等就跳过这个数避免重复计算。 ✍ 最优解——双指针法实现代码如下 class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort() # 对数组进行排序n len(nums)ans []for i in range(n):if i 0 and nums[i] nums[i - 1]: # 跳过重复的数continuel, r i 1, n - 1 # 双指针初始值while l r:if nums[l] nums[r] nums[i] 0: # 找到一组符合条件的数ans.append([nums[i], nums[l], nums[r]]) # 添加到结果集中while l r and nums[l] nums[l 1]: # 跳过重复的数l 1while l r and nums[r] nums[r - 1]: # 跳过重复的数r - 1l 1 # 左指针右移r - 1 # 右指针左移elif nums[l] nums[r] nums[i] 0: # 三数之和小于0l 1 # 左指针右移else: # 三数之和大于0r - 1 # 右指针左移return ans # 返回结果上述代码的详细实现步骤如下
首先对数组进行排序方便后续处理遍历数组中的每个数作为三元组中的第一个数对于每个三元组中的第一个数使用双指针来找到剩余两个数在双指针中l 指向当前三元组中的第二个数r 指向当前三元组中的第三个数当三个数的和等于0时即找到了一个符合要求的三元组将其添加到答案数组中并分别将 l 和 r 向中间移动一位跳过重复的数当三个数的和小于0时将 l 向右移动一位尝试增大当前三元组的和当三个数的和大于0时将 r 向左移动一位尝试减小当前三元组的和最后返回答案数组。
除了双指针算法之外还有一些其他的解决方法如哈希表、暴力枚举等。但是在时间复杂度和空间复杂度方面双指针算法是效率最高的解决方法。
下面我给出暴力枚举法和哈希表法供大家学习参考。
暴力枚举法
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:n len(nums)ans []# 枚举三个数的组合for i in range(n):for j in range(i1, n):for k in range(j1, n):if nums[i] nums[j] nums[k] 0:ans.append([nums[i], nums[j], nums[k]])ans [list(t) for t in set(tuple(lst) for lst in ans)] # 去重return ans这种方法的时间复杂度较高不适合处理较大的数据集但对于小数据集可以得到正确的结果。
哈希表法
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:n len(nums)ans []hash_table {}for i in range(n):hash_table[nums[i]] ifor i in range(n):for j in range(i1, n):if -nums[i]-nums[j] in hash_table and hash_table[-nums[i]-nums[j]] j:ans.append([nums[i], nums[j], -nums[i]-nums[j]])ans [list(t) for t in set(tuple(lst) for lst in ans)] # 去重return ans更推荐大家去使用双指针法来解决这个问题。
B站上面卡尔老师对于这道题的解题思路是使用第一种的双指针法解决讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1GW4y127qo/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34 7、四数之和 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序返回答案 。
示例1
输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例2
输入nums [2,2,2,2,2], target 8
输出[[2,2,2,2]]提示
1 nums.length 200
-109 nums[i] 109
-109 target 109这道题在三数之和的基础上又添加了一个数而且是在同一个数组中更加麻烦是第 15 题 **三数之和** 的进阶版可以采用类似的方法解决。我们仍然可以采用暴力枚举、双指针、哈希表等方法解决。 暴力枚举法我们可以使用四重循环来枚举四个元素这种方法的时间复杂度为 O(n4)O(n^4)O(n4)不太可取。
这里我们只讲一下其中的双指针法和哈希表。
其中双指针法具体思路和代码实现可以参考第 15 题 三数之和 的解题思路先对数组进行排序然后在数组中枚举第一个数在剩下的数中使用双指针的方法寻找满足条件的另外两个数使得三个数的和等于 target。在寻找的过程中为了避免重复的解需要加入一些特判和判断。
然后哈希表法是先将数组 nums 中的两个元素相加将它们的和作为哈希表的键它们的下标作为哈希表的值。接下来遍历数组 nums 中的另外两个元素如果它们的和等于 target 减去哈希表中的键就说明找到了符合要求的四元组。 ✍ 使用双指针法解决 class Solution:def fourSum(self, nums: List[int], target: int) - List[List[int]]:n len(nums)if n 4: # 数组长度小于 4 时直接返回空列表return []nums.sort() # 对数组进行排序res [] # 存储结果的列表for i in range(n-3): # 枚举第一个数if i 0 and nums[i] nums[i-1]: # 跳过重复的数continueif nums[i] nums[i1] nums[i2] nums[i3] target: # 如果当前的最小值都大于 target则结束breakif nums[i] nums[n-3] nums[n-2] nums[n-1] target: # 如果当前的最大值都小于 target则跳过continuefor j in range(i1, n-2): # 枚举第二个数if j i1 and nums[j] nums[j-1]: # 跳过重复的数continueif nums[i] nums[j] nums[j1] nums[j2] target: # 如果当前的最小值都大于 target则结束breakif nums[i] nums[j] nums[n-2] nums[n-1] target: # 如果当前的最大值都小于 target则跳过continueleft, right j1, n-1 # 双指针初始值while left right: # 双指针遍历temp_sum nums[i] nums[j] nums[left] nums[right] # 计算当前四数之和if temp_sum target: # 如果等于 target则加入结果并跳过重复的数res.append([nums[i], nums[j], nums[left], nums[right]])while left right and nums[left] nums[left1]:left 1while left right and nums[right] nums[right-1]:right - 1left 1right - 1elif temp_sum target: # 如果小于 target则左指针右移left 1else: # 如果大于 target则右指针左移right - 1return res # 返回结果列表在上述代码中我们首先对数组进行排序然后依次枚举前两个数的下标 i 和 j。在每次枚举中我们通过双指针的方式从剩下的数中找到另外两个数使得四数之和等于目标值 target。在这个过程中需要注意以下几点
为了避免重复我们需要对每一个枚举到的数都跳过所有与之前枚举到的数相同的情况。当四数之和小于目标值时需要将左指针右移一位以使得和变大当四数之和大于目标值时需要将右指针左移一位以使得和变小。对于重复的数我们只需将指针移动到第一个不同的数处即可。
最终我们可以得到所有不重复的四元组使得它们的和等于目标值 target。
使用哈希表解决
class Solution(object):def fourSum(self, nums, target):# 创建一个哈希表记录每个数字出现的次数。hashmap dict()for n in nums:if n in hashmap:hashmap[n] 1else: hashmap[n] 1# 创建一个空的集合用于存储结果。ans set()# 使用三重循环枚举三个数ijk其中ijk。for i in range(len(nums)):for j in range(i 1, len(nums)):for k in range(j 1, len(nums)):# 计算目标值与三个数之和的差值判断该差值是否在哈希表中存在。val target - (nums[i] nums[j] nums[k])if val in hashmap:# 计算差值在三个数中出现的次数如果大于等于当前哈希表中该差值的出现次数则将四个数进行排序并添加到集合中。count (nums[i] val) (nums[j] val) (nums[k] val)if hashmap[val] count:ans_tmp tuple(sorted([nums[i], nums[j], nums[k], val]))ans.add(ans_tmp)else:continue# 返回集合的列表形式作为最终结果。return list(ans)B站上面卡尔老师对于这道题的解题思路是使用第一种的双指针法解决讲得很不错在这里推荐大家去看看他的教学视频
https://www.bilibili.com/video/BV1DS4y147US/?spm_id_from333.788vd_sourceeae0406d86828f39f6ac3a3b0e8a2a34
四、如何选择哈希表实现对象
在上面的题目中我们在定义选择哈希表的实现对象的时候是不一样的有些朋友可能就会好奇我们什么时候选择数组作为哈希表更好什么时候选择set作为哈希表更好什么时候选择map作为哈希表更好
下面我来做一个总结仅供参考
数组作为哈希表 如果题目中明确说明了数据的范围可以直接利用数组实现哈希表。例如当题目要求哈希表中的键即数组中的元素取值范围为[0, 100]时可以定义长度为101的数组作为哈希表键值为i的元素就存放在下标为i的位置上。这种方法的时间复杂度为O(1)是最快的但需要额外的空间来存储数组。set作为哈希表 如果不需要对哈希表中的键进行计数而只是需要判断某个元素是否存在于哈希表中可以使用set作为哈希表。这种方法的时间复杂度为O(1)比使用数组作为哈希表更节省空间。map作为哈希表 如果需要对哈希表中的键进行计数可以使用map作为哈希表。map可以实现键值对的映射并记录每个键在哈希表中出现的次数。这种方法的时间复杂度为O(1)但空间开销较大。
在实际应用中我们需要根据题目的要求来选择适合的哈希表实现对象。具体而言当哈希表中的键取值范围不大且需要对键进行计数时可以选择数组或map作为哈希表当哈希表中的键取值范围较大且只需要判断键是否存在时可以选择set作为哈希表。
表格总结如下
哈希表实现对象适用场景时间复杂度空间复杂度数组键取值范围小需要对键进行计数O(1)额外空间set键取值范围大只需判断键是否存在O(1)额外空间map键取值范围小或大需要对键进行计数且不需要自定义哈希函数O(1)额外空间
