本文主要是介绍【LeetCode最详尽解答】15-三数之和 3sum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家!
链接:
- 15-三数之和
直觉
示例:
输入: 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]
。
注意输出的顺序和三元组的顺序无关。
首先,我们应该记住,解决方案集不得包含重复的三元组。考虑这个示例 [-3, 3, 4, -3, 1, 2]
,我们需要找到 _+_+_ = 0
。如果我们先看索引 0,那么它将填充 -3(索引[0]) + 1 + 2 = 0。但是,当我们到达索引 3 时,它仍然具有相同的组合,即 -3(索引[3]) + 1 + 2 = 0。这就是重复的。因此,我们可以首先对数组进行排序来处理它。在这种情况下,它将排序为 [-3, -3, 1, 2, 3, 4]
,当我们遇到第二个 -3 时,我们可以跳过它。
对于 _+_+_ = 0
,当我们选择第一个元素时,我们需要在剩余排序数组中找到两个元素,它们的和等于负的第一个元素值。然后它转换为一个两数之和的问题,类似于问题 167-两数之和 II-输入数组已排序,即在排序数组中找到两个数的和。在此示例中,排序后的数组将变为 [-4, -1, -1, 0, 1, 2]
,我们应该遍历整个数组,找到 -4 + [-1, -1, 0, 1, 2] = 0,然后 -1 + [-1, 0, 1, 2] = 0,然后跳过第二个 -1,然后 0 + [1, 2] = 0,等等。
当我们遍历整个数组时,我们还应该添加一些基本情况。如果 nums[i] > 0
,那么我们中断,因为数组是递增顺序的。如果 nums[i] == nums[i-1]
,我们应该继续循环,因为如果我们不进行此操作,答案将重复。考虑 [-1, -1, 0, 1, 2]
。对于第一个 -1,它将有 [-1, -1, 2]
和 [-1, 0, 1]
。对于第二个 -1,它也将有 [-1, 0, 1]
,这会重复答案。因为第一个 -1 的剩余数组包含了第二个 -1 的剩余数组。
然后我们可以处理这个问题。让两个指针指向剩余数组的开始和结束位置:左指针为 i + 1
,右指针为数组的末尾位置。如果这三个值小于 0,那么将 l
向右移动。如果这三个值大于 0,那么将 r
向左移动。否则,我们可以将这三个值追加到结果中。之后,我们应该增加左指针并减少右指针,因为数组不仅包含一个解决方案。然而,为了避免重复的解决方案,我们还需要做一个额外的步骤。考虑 -1[0, 0, 0, 1, 1]
。如果 left+1,我们移动到第二个 0 和第一个 1。那么,因为第二个 0 与第一个 0 是相同的值,我们不能将其视为额外的解决方案。我们应该继续将左指针向右移动且不超过右指针。最后,左指针将位于第一个 1,与右指针在同一位置,它将不会进入 while l < r
循环,结果不会追加它。
方法
- 对数组进行排序。
- 遍历排序后的数组,对于每个索引,将剩余元素转换为两数之和问题。
- 通过在处理两数之和问题时检查
nums[l] == nums[l-1]
,以及在选择基值时检查nums[i] == nums[i-1]
来避免重复的解决方案。 - 最后,返回结果。
复杂度
- 时间复杂度:
O ( n 2 ) O(n^2) O(n2)- 对数组进行排序需要 O ( n log n ) O(n \log n) O(nlogn),并且在循环中使用双指针方法需要 O ( n 2 ) O(n^2) O(n2),
复杂度
-
时间复杂度:
O ( n 2 ) O(n^2) O(n2)- 对数组进行排序需要 O ( n log n ) O(n \log n) O(nlogn),并且在循环中使用双指针方法需要 O ( n 2 ) O(n^2) O(n2),因此总体时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
-
空间复杂度:
O ( n ) O(n) O(n)- 如果不考虑用于存储输出的空间,空间复杂度为 O ( 1 ) O(1) O(1)。排序是就地完成的,只使用常量量的额外空间。
代码
class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""nums.sort()result = []for i in range(len(nums)):if nums[i] > 0:breakif i > 0 and nums[i] == nums[i-1]:continuel = i+1r = len(nums) - 1while l < r:if nums[i] + nums[l] + nums[r] < 0:l+=1elif nums[i] + nums[l] + nums[r] > 0:r-=1else:result.append([nums[i], nums[l], nums[r]])l+=1r-=1while nums[l] == nums[l-1] and l < r:l+=1return result
这篇关于【LeetCode最详尽解答】15-三数之和 3sum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!