什么网站做推广比较好,两学一做网站无法做题,导航网站教程,泰州网站建设方案文章目录 引言三数之和题目描述示例示例1示例2示例3 提示 解决方案3#xff1a;【双指针】结束语 三数之和 引言
编写通过所有测试案例的代码并不简单#xff0c;通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例#xff0c;但如果不了解代码背后的思考过程… 文章目录 引言三数之和题目描述示例示例1示例2示例3 提示 解决方案3【双指针】结束语 三数之和 引言
编写通过所有测试案例的代码并不简单通常需要深思熟虑和理性分析。虽然这些代码能够通过所有的测试案例但如果不了解代码背后的思考过程那么这些代码可能并不容易被理解和接受。我编写刷题笔记的初衷是希望能够与读者们分享一个完整的代码是如何在逐步的理性思考下形成的。我非常欢迎读者的批评和指正因为我知道我的观点可能并不完全正确您的反馈将帮助我不断进步。如果我的笔记能给您带来哪怕是一点点的启示我也会感到非常荣幸。同时我也希望我的分享能够激发您的灵感和思考让我们一起在编程的道路上不断前行~
三数之和
题目描述
给你一个整数数组 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
解决方案3【双指针】
在博客【LeetCode刷题笔记6-1】【Python】【三数之和】【哈希表】【中等】中我们详尽地探讨了如何利用【哈希表】精妙设计算法从而顺利通关【三数之和】这一挑战。
在此过程中我们深度挖掘了问题细节确保算法能够通过所有的测试案例(基于哈希表设计的算法在【三数之和】上很容易超时) — 这不仅是一次技术上的磨练更是对细心与耐心的极致考验。
问题1为什么【三数之和】问题可以用【双指针】来解决
在博客【LeetCode刷题笔记6-1】【Python】【三数之和】【哈希表】【中等】中我们从两数之和的解决方案中汲取灵感通过举一反三巧妙地运用哈希表来解决【三数之和】问题。而对于【双指针】的使用背后又隐藏着怎样的深刻逻辑呢— 先回到三数之和的本质查找目标值。
在【哈希表】解决方案中我们通过两层遍历的方式首先固定两个值然后利用哈希表快速查找剩下的一个值。那么除了哈希表外是否还有其他算法可以达到类似的效果呢答案是肯定的那就是双指针方法。
通过固定一个值然后使用双指针在数组中查找剩余的两个值同样可以达到解决问题的目的。这种方法的优势在于它避免了哈希表的开销同时保持了查找的效率。
我们可以把双指针分为左指针left和右指针right。在循环遍历数组nums的每个元素nums[i]时设计算法找到正确的nums[left]和nums[right], 共同组成满足题意的三元组[nums[i], nums[left], nums[right]]。
代码的初始版本如下
class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: # 如果输入的数组为空或长度小于3直接返回空列表 if not nums or len(nums) 3: return [] # 对输入的数组进行排序nums.sort() # 获取列表的长度 n len(nums) # 初始化结果列表 result_list [] # 遍历数组中的每个元素 -- 固定元素nums[i]for i in range(n): # 初始化左指针和右指针分别指向剩余两个元素的位置 left 0 right n - 1 # 当左指针小于右指针时进行循环 while left right: # 如果三个元素的和等于0则将这三个元素添加到结果列表中并同时移动左指针和右指针if nums[i] nums[left] nums[right] 0: result_list.append([nums[i], nums[left], nums[right]]) left 1 # 左指针右移right - 1 # 右指针左移 # 如果三个元素的和大于0则右指针向左移动以减少和的值 elif nums[i] nums[left] nums[right] 0: right - 1 else: # 如果三个元素的和小于0则左指针向右移动以增加和的值 left 1 return result_list # 返回结果列表初步运行结果 可以看到虽然结果列表中包含了正确的三元组但更多的是重复的三元组(如上图的蓝色框部分)甚至还出现重复利用数组元素的三元组(上图红色框重复利用元素2)。
尽管初始的代码版本问题很大但还是有一些小细节值得拎出来说明一下
细节1为什么要对数组nums进行排序
如果您已看完这篇博客您会知道其中一个原因是为了方便去重。但目前的【初始代码】压根与去重无关。其实现阶段对数组nums进行排序的原因是为了方便确定左指针left和右指针right的移动方向。
如果数组nums是乱序的如果nums[i] nums[left] nums[right] 0下一步是移动左指针还是右指针显然是不确定的。如果数组nums是有序的比如说从小到大排列。那么left右移 三元组之和将增加同理right左移 三元组之和将减少那么nums[i] nums[left] nums[right] 0下一步自然是right左移使三元组之和进一步接近0。
从细节1的分析中我们可以看出对数组nums进行排序对于应用双指针算法解决三数之和问题至关重要。甚至可以说方便去重只是这个过程中的一个额外的好处就像“买一送一”一样。
细节2while left right: 这个语句能否取等即while left right:
不能。我们可以从左右指针的定义中找到答案 分别指向剩余两个元素的位置。如果left right成立 ⇒ 三元组会包含同一元素
细节3当三元组元素满足nums[i] nums[left] nums[right] 0时为什么下一步要同时进行left右移和right左移
如果我们只进行left右移相当于nums[i] 和 nums[left]是固定的。想要nums[i] nums[left] nums[right] 0继续成立nums[right]即使元素位置变了但元素值不可能变 只移动一个指针没有意义都不移动更没有意义 — 同时进行left右移和right左移。
想清楚三个细节后紧接着就要思考为什么这个代码会生成这么多重复的三元组甚至还出现重复利用数组元素的三元组
问题1左指针left不应该初始化为0
如果我们把左指针left初始化为0 ⇒ 在【双指针】查找剩余两个元素时左指针left的右移和右指针right的左移都可能碰上事先固定的元素nums[i] ⇒ 出现重复利用数组元素的三元组。既然0不行那么初始化为[0, i]的任何数都会出现这样的问题。
那将左指针left初始化为i1 是的这样既可以保证左指针left的右移和右指针right的左移不可能会碰到事先固定的元素nums[i]也不会出现遗漏某个三元组的情况。
代码如下见修改1
class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: # 如果输入的数组为空或长度小于3直接返回空列表 if not nums or len(nums) 3: return [] # 对输入的数组进行排序nums.sort() # 获取列表的长度 n len(nums) # 初始化结果列表 result_list [] # 遍历数组中的每个元素 -- 固定元素nums[i]for i in range(n): # 初始化左指针和右指针 分别指向剩余两个元素的位置 left i 1 # 修改1初始化为i1right n - 1 # 当左指针小于右指针时进行循环 while left right: # 如果三个元素的和等于0则将这三个元素添加到结果列表中并同时移动左指针和右指针if nums[i] nums[left] nums[right] 0: result_list.append([nums[i], nums[left], nums[right]]) left 1 # 左指针右移right - 1 # 右指针左移 # 如果三个元素的和大于0则右指针向左移动以减少和的值 elif nums[i] nums[left] nums[right] 0: right - 1 else: # 如果三个元素的和小于0则左指针向右移动以增加和的值 left 1 return result_list # 返回结果列表运行结果 可以看到相比于上一版代码这一版结果虽然仍然存在重复的三元组但已经没有出现重复利用数组元素的三元组— 这是由于这版代码中, i left right的关系是恒成立的保证了不可能重复利用数组元素。
问题2为什么仍然存在重复的三元组[-1, 0, 1]呢
数组[-1,0,1,2,-1,-4]排序后的结果为[-4, -1, -1, 0, 1, 2] ⇒ 当遍历数组元素依次固定元素值时元素-1会连续两次作为固定的值 ⇒ 结果列表中多了一个三元组
由于数组是有序的我们可以很简单的对这种情况进行去重操作代码如下(见修改2)
class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: # 如果输入的数组为空或长度小于3直接返回空列表 if not nums or len(nums) 3: return [] # 对输入的数组进行排序nums.sort() print(nums)# 获取列表的长度 n len(nums) # 初始化结果列表 result_list [] # 遍历数组中的每个元素 -- 固定元素nums[i]for i in range(n):# 修改2去除连续相同的元素值if i 0 and nums[i] nums[i-1]:continue# 初始化左指针和右指针 分别指向剩余两个元素的位置 left i 1 # 修改1初始化为i1right n - 1 # 当左指针小于右指针时进行循环 while left right: # 如果三个元素的和等于0则将这三个元素添加到结果列表中并同时移动左指针和右指针if nums[i] nums[left] nums[right] 0: result_list.append([nums[i], nums[left], nums[right]]) left 1 # 左指针右移right - 1 # 右指针左移 # 如果三个元素的和大于0则右指针向左移动以减少和的值 elif nums[i] nums[left] nums[right] 0: right - 1 else: # 如果三个元素的和小于0则左指针向右移动以增加和的值 left 1 return result_list # 返回结果列表运行结果 可以看到目前代码已经通过132个测试用例但仍然会出现重复的三元组。
问题3为什么仍然存在重复的三元组[-2, 0, 2]呢我们可以从排序后的数组[-2, 0, 0, 2, 2]看出0和2分别重复了两次 ⇒ 当我们固定元素-2时并快速找到[-2, 0, 2]这个正确的三元组此时左指针left右移右指针right左移。巧的是左指针left依然指向元素0右指针依然指向元素2 ⇒ 出现重复的三元组[-2, 0, 2]。
因此我们在找到正确三元组的同时应该把与左指针left指向的元素相同的过滤掉也把与右指针right指向的元素相同的过滤掉。代码如下见修改3
class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: # 如果输入的数组为空或长度小于3直接返回空列表 if not nums or len(nums) 3: return [] # 对输入的数组进行排序nums.sort() print(nums)# 获取列表的长度 n len(nums) # 初始化结果列表 result_list [] # 遍历数组中的每个元素 -- 固定元素nums[i]for i in range(n):# 修改2去除连续相同的元素值if i 0 and nums[i] nums[i-1]:continue# 初始化左指针和右指针 分别指向剩余两个元素的位置 left i 1 # 修改1初始化为i1right n - 1 # 当左指针小于右指针时进行循环 while left right: # 如果三个元素的和等于0则将这三个元素添加到结果列表中并同时移动左指针和右指针if nums[i] nums[left] nums[right] 0: result_list.append([nums[i], nums[left], nums[right]]) # 修改3while left right and nums[left] nums[left1]: left 1 # 如果左边的元素相等则移动左指针 while left right and nums[right] nums[right-1]: right - 1 # 如果右边的元素相等则移动右指针 left 1 # 左指针右移right - 1 # 右指针左移 # 如果三个元素的和大于0则右指针向左移动以减少和的值 elif nums[i] nums[left] nums[right] 0: right - 1 else: # 如果三个元素的和小于0则左指针向右移动以增加和的值 left 1 return result_list # 返回结果列表运行结果 可以看到目前代码已经能够通过所有测试案例但代码运行时间显然还是比较长的。
问题4还有没有进一步优化的可能性
有的。
首先数组nums是排好序的而我们的目标是找三个元素让它们的和为0 ⇒ 如果当前固定的值为nums[i] 0 ⇒ 根据i left right, 即nums[i] nums[i] nums[i]恒成立不可能找到和为0的三元组此时应该直接返回结果。
问题5nums[i] 0 的情况是否要保留即返回条件是否可改为nums[i] 0
不可以因为可能存在[0, 0, 0]这个正确的三元组代码如下见修改4
完整代码
class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: # 如果输入的数组为空或长度小于3直接返回空列表 if not nums or len(nums) 3: return [] # 对输入的数组进行排序nums.sort() # print(nums)# 获取列表的长度 n len(nums) # 初始化结果列表 result_list [] # 遍历数组中的每个元素 -- 固定元素nums[i]for i in range(n):# 修改2去除连续相同的元素值if i 0 and nums[i] nums[i-1]:continue# 修改4 if nums[i] 0:return result_list# 初始化左指针和右指针 分别指向剩余两个元素的位置 left i 1 # 修改1初始化为i1right n - 1 # 当左指针小于右指针时进行循环 while left right: # 如果三个元素的和等于0则将这三个元素添加到结果列表中并同时移动左指针和右指针if nums[i] nums[left] nums[right] 0: result_list.append([nums[i], nums[left], nums[right]]) # 修改3while left right and nums[left] nums[left1]: left 1 # 如果左边的元素相等则移动左指针 while left right and nums[right] nums[right-1]: right - 1 # 如果右边的元素相等则移动右指针 left 1 # 左指针右移right - 1 # 右指针左移 # 如果三个元素的和大于0则右指针向左移动以减少和的值 elif nums[i] nums[left] nums[right] 0: right - 1 else: # 如果三个元素的和小于0则左指针向右移动以增加和的值 left 1 return result_list # 返回结果列表运行结果
复杂度分析
时间复杂度O(N2)其中 N 是数组nums元素的数量。空间复杂度O(N) 存放数组排序后的新数组 O(N)
结束语
亲爱的读者感谢您花时间阅读我们的博客。我们非常重视您的反馈和意见因此在这里鼓励您对我们的博客进行评论。您的建议和看法对我们来说非常重要这有助于我们更好地了解您的需求并提供更高质量的内容和服务。无论您是喜欢我们的博客还是对其有任何疑问或建议我们都非常期待您的留言。让我们一起互动共同进步谢谢您的支持和参与我会坚持不懈地创作并持续优化博文质量为您提供更好的阅读体验。谢谢您的阅读
