北京市著名的网站制作公司,盐城做网站spider net,天津市网站建设天津商城建设,网站内容架构拓扑怎么做文章目录 引言三数之和题目描述示例示例1示例2示例3 提示 解决方案1#xff1a;【三层遍历查找】解决方案2#xff1a;【哈希表】【两层遍历】结束语 三数之和 引言
编写通过所有测试案例的代码并不简单#xff0c;通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的… 文章目录 引言三数之和题目描述示例示例1示例2示例3 提示 解决方案1【三层遍历查找】解决方案2【哈希表】【两层遍历】结束语 三数之和 引言
编写通过所有测试案例的代码并不简单通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例但如果不了解代码背后的思考过程那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正因为我知道我的观点可能并不完全正确您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示我也会感到非常荣幸。同时我也希望我的分享能够激发您的灵感和思考让我们一起在编程的道路上不断前行~
三数之和
题目描述
给你一个整数数组 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]]
示例2
输入nums [0,1,1]输出[]解释唯一可能的三元组和不为 0 。
示例3
输入nums [0,0,0]输出[[0,0,0]]解释唯一可能的三元组和为 0 。
提示
3 nums.length 3000-105 nums[i] 105
解决方案1【三层遍历查找】
对于解决【三数之和】这个问题一种直观的解法是三层循环枚举所有可能的三元组然后判断它们的和是否为零但是这样的时间复杂度是 O(n3)对于较大的数组来说是不可接受的。
解决方案2【哈希表】【两层遍历】
在探讨【三数之和】这一算法题之前我相信许多读者已经对【两数之和】有所涉猎。在我们深入理解题目要求时我们明确了解决【两数之和】问题的核心是【如何高效查找目标值】。而【哈希表】以其迅速的查找速度脱颖而出成为解决此类问题的得力助手。
现在摆在我们面前的是【三数之和】问题它与【两数之和】有着诸多相似之处。因此我们很自然地会联想到运用【哈希表】来助力解决。这种思维跳跃不仅体现了我们对已知知识的灵活运用更展示了我们在面对新问题时的敏捷思维。
与【三层遍历】相比【哈希表】是一种以空间换时间的解决方案。首先数组nums中可能存在大量值相同但索引不同的元素如下所示
nums1 [0] * 10 [1] * 10 [-1] * 10
print(nums1)
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1]对于这个问题而言这些大量重复的元素显然是冗余的。我们的核心目标是在数组中找到N个不重复的三元组在这些三元组中元素之和为0 除了[0, 0, 0]这种特殊情况其它任何数都不可能在一个三元组中重复三次(和不可能为0)。那么nums1实际上等价于数组[0, 0, 0, 1, 1, -1, -1] 这意味着我们可以先对原数组nums先进行【去重】操作形成一个新数组new_nums在新数组中除了0可以重复三次其它值至多重复两次。
原数组【去重】的重要意义某些情况可以显著降低整体算法的时间复杂度。比如说上面代码里的nums1原来有30个元素那么两层循环遍历的时间复杂度是O(n2)n30; 如果对nums1进行去重去重后的新数组实际上只包含7个元素两层循环遍历的时间复杂度从O(302)将至O(72)
原数组【去重】代码如下
# 创建哈希表记录去重后的新数组元素方便后续遍历查找目标值。
hash_map {} # 哈希表的键为新数组元素值值为元素值在新数组的新下标num_idx
num_idx 0 # 新数组的下标初始化为0
new_nums [] # 用新的数组记录去重后的数组# 遍历原数组
for idx, num in enumerate(nums): # 当前元素不在哈希表中if num not in hash_map:hash_map[num] [num_idx] # 创建新的键-值对记录该元素# 记录去重后仍保留的数组元素new_nums.append(num) num_idx 1 else: # 当前元素已在哈希表中# 如果该元素已在哈希表中记录两次if len(hash_map[num]) 2:if num 0: # 除非该元素是0否则不再记录hash_map[num].append(num_idx)new_nums.append(num)num_idx 1# 如果该元素已在哈希表中记录一次elif len(hash_map[num]) 1:# 在哈希表中再次记录该元素hash_map[num].append(num_idx)# 新数组同时记录该元素new_nums.append(num)num_idx 1# 其它情况不做任何处理else:pass当有了哈希表hash_map后便可以通过【两层遍历】在哈希表中查找目标值来得到有效的三元组。
算法步骤
第一层循环遍历数组元素nums[i] — i从0–nn为新数组的元素个数执行步骤(2)第二层循环遍历数组元素nums[j] — j从i1–nn为新数组的元素个数执行步骤(3)若nums[i] nums[j]的相反数-(nums[i] nums[j])不存在于哈希表hash_map中则返回步骤(1; 若存在说明找到可能正确的三元组执行步骤(4)遍历哈希表中键【-(nums[i] nums[j])】对应的每个索引k — k至多有三个不同的值(分别是三个0元素所对应的索引)执行步骤(5);若ki或者kj, 说明这个元素三元组将出现重复的元素(同一索引)不符合题意返回步骤(1— 第一次去重避免在元素三元组中出现同一元素同索引的元素 若k!i and k!j说明当前的三个索引i,j,k互不相同可能是正确的三元组执行步骤(6) 【细节】尽管三个索引i,j,k互不相同但仍然不能保证由索引三元组对应的元素三元组不会在结果列表中出现重复 — 不同的索引三元组可能对应同一种元素三元组;参考字母异位词分组的解决方案对当前三个索引所生成的结果列表[new_nums[k], new_nums[i], new_nums[j]]进行【排序】。因为一旦出现重复的三元组结果(如[1, 0, -1] 和[0, 1, -1])它们虽然顺序不同但排序结果一定是相同 检查排序后的元素三元组sorted_result是否存在于哈希表is_used_results中若已存在说明出现了重复的元素三元组不符合题意返回步骤(1— 第二次去重避免出现重复的元素三元组尽管三个索引i,j,k互不相同 若不存在说明这个元素三元组是无重复的执行步骤(7)将元素三元组保存于结果列表result_list中重复执行步骤1-7直到循环结束。
【细节】既然已经有一个结果列表result_list记录元素三元组为什么不直接判断排序后的元素三元组sorted_result是否存在于结果列表result_list中而是重新创建一个哈希表is_used_results来协助判断
答因为哈希表的查找速度非常快如果在列表中查找可能会超时
完整代码如下
class Solution: def threeSum(self, nums: List[int]) - List[List[int]]:# 创建哈希表记录去重后的新数组元素方便后续遍历查找目标值。hash_map {} # 哈希表的键为新数组元素值值为元素值在新数组的新下标num_idxnum_idx 0 # 新数组的下标初始化为0new_nums [] # 用新的数组记录去重后的数组# 遍历原数组for idx, num in enumerate(nums): # 当前元素不在哈希表中if num not in hash_map:hash_map[num] [num_idx] # 创建新的键-值对记录该元素# 记录去重后仍保留的数组元素new_nums.append(num) num_idx 1 else: # 当前元素已在哈希表中# 如果该元素已在哈希表中记录两次if len(hash_map[num]) 2:if num 0: # 除非该元素是0否则不再记录hash_map[num].append(num_idx)new_nums.append(num)num_idx 1# 如果该元素已在哈希表中记录一次elif len(hash_map[num]) 1:# 在哈希表中再次记录该元素hash_map[num].append(num_idx)# 新数组同时记录该元素new_nums.append(num)num_idx 1# 其它情况不做任何处理else:passresult_list [] # 存放元素三元组n len(new_nums) is_used_results set() # 创建哈希表协助判断元素三元组是否重复for i in range(n): for j in range(i1, n): if -(new_nums[i] new_nums[j]) in hash_map: for k in hash_map[-(new_nums[i] new_nums[j])]: # 查找目标值, 依次返回目标值索引kif k i:continue # 第一次去重避免元素三元组出现重复的元素elif k j:continue # 第一次去重避免元素三元组出现重复的元素else:sorted_result tuple(sorted([new_nums[k], new_nums[i], new_nums[j]]))if sorted_result in is_used_results: # 涉及查找时用哈希表最快pass # 第二次去重避免结果列表中出现重复的元素三元组else:result_list.append([new_nums[k], new_nums[i], new_nums[j]]) is_used_results.add(sorted_result) return result_list运行结果 复杂度分析
时间复杂度O(N2)其中 N 是新数组new_nums元素的数量。 双层循环遍历新数组 O(N2) 空间复杂度O(N) 需要用哈希表和列表存放新数组 O(N)
结束语
亲爱的读者感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见因此在这里鼓励您对我们的博客进行评论。您的建议和看法对我们来说非常重要这有助于我们更好地了解您的需求并提供更高质量的内容和服务。无论您是喜欢我们的博客还是对其有任何疑问或建议我们都非常期待您的留言。让我们一起互动共同进步谢谢您的支持和参与我会坚持不懈地创作并持续优化博文质量为您提供更好的阅读体验。谢谢您的阅读
