题目:
给你一个整数数组 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 。
Python3代码解答:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# 创建一个空列表result用来存放满足条件的三元组
result = []
# 给数组排序
nums.sort()
# 遍历数组
for i in range(len(nums)):
# 如果当前元素大于0,那么排序后的元素必定都大于0
if nums[i] > 0:
return result
# 如果当前元素和上一个元素相同,则跳过当前循环
# 如果 nums[i] 和 nums[i-1] 相同,那么基于 nums[i-1] 已经尝试过的所有
# 可能的 left 和 right ,组合也会和基于 nums[i] 的组合重复
if i > 0 and nums[i] == nums[i - 1]:
continue
# 设置两个指针,分别指向i之后的下一个元素和最后一个元素
left = i + 1
right = len(nums) - 1
while right > left:
# 计算三元组的和
sum_ = nums[i] + nums[left] + nums[right]
if sum_ < 0:
# 如果 sum_ 小于 0,表示需要更大的数来抵消负数,因此将 left 指针向右移动一位
left += 1
elif sum_ > 0:
# 如果 sum_ 大于 0,表示需要更小的数来减小总和,因此将 right 指针向左移动一位
right -= 1
else:
# 如果 sum_ 等于 0,将当前三元组 [nums[i], nums[left], nums[right]]
# 加入到结果列表 result
result.append([nums[i], nums[left], nums[right]])
# 在找到一个和为 0 的三元组后,为了避免添加重复的三元组
# 需要在移动 left 和 right 指针之前跳过所有相同的元素
# 如果 nums[right] 和它前一个元素 nums[right - 1] 相同,
# 则 right 指针会继续向左移动
while right > left and nums[right] == nums[right - 1]:
right -= 1
# 如果 nums[left] 和它后一个元素 nums[left + 1] 相同,
# left 指针会继续向右移动,直到 nums[left] 的值改变
# 这同样是为了防止因 left 指针位置的重复值导致的三元组重复
while right > left and nums[left] == nums[left + 1]:
left += 1
# 完成这两个循环过后,指针 right 和 left 应该指向新的、非重复的元素
# 然而,我们还需要进一步地将这两个指针分别向内移动一位
right -= 1
left += 1
return result
上述代码解答:
上述代码实现的是 threeSum
方法,用于在给定整数数组 nums
中找出所有不重复的三元组(i.e., 三个数的组合),这些三元组的和为 0。方法的具体实现步骤如下:
初始化结果列表:创建一个空列表
result
用来存放满足条件的三元组。排序数组:首先对数组
nums
进行排序。排序是为了之后更容易地使用双指针技术查找和为0的三元组。遍历数组:通过一个 for 循环遍历排序后的数组,索引为
i
。该索引代表三元组中的第一个数。提前停止条件:如果当前元素
nums[i]
大于 0,由于数组已经排序,后面的所有元素都会大于 0,因此不可能再找到和为 0 的三元组,直接返回已找到的结果result
。避免重复元素:为了避免找到重复的三元组,如果当前元素与前一个元素相同(
nums[i] == nums[i - 1]
),则跳过当前循环的迭代。双指针查找:设置两个指针
left
和right
,分别指向i
之后的下一个元素和数组的最后一个元素。这两个指针会帮助找到与nums[i]
相加和为 0 的两个数。双指针移动:
- 计算当前三元组的和
sum_
。如果sum_
小于 0,表示需要更大的数来抵消负数,因此将left
指针向右移动一位。 - 如果
sum_
大于 0,表示需要更小的数来减小总和,因此将right
指针向左移动一位。 - 如果
sum_
等于 0,将当前三元组 [nums[i], nums[left], nums[right]] 加入到结果列表result
。
- 计算当前三元组的和
避免添加重复的三元组:在找到一个和为 0 的三元组后,为了避免添加重复的三元组,需要在移动
left
和right
指针之前跳过所有相同的元素。结果返回:循环结束后,返回结果列表
result
,其中包含了所有不重复的和为 0 的三元组。
重难点解答:
解释如何在 threeSum
方法中避免添加重复的三元组:
1. 排序
首先,对数组进行排序是基础,它使得相同的数字都相邻,这有助于后续步骤中识别和跳过重复的元素。
2. 跳过处理中的重复元素
为了确保不添加重复的三元组,有两种主要的情况需要处理:
a. 跳过相同的起始元素
当遍历数组以选择三元组的第一个元素 nums[i]
时,如果当前的元素和前一个元素相同(即 nums[i] == nums[i-1]
),并且 i
大于 0,则跳过当前的元素。这是因为如果 nums[i]
和 nums[i-1]
相同,那么基于 nums[i-1]
已经尝试过的所有可能的 left
和 right
组合也会和基于 nums[i]
的组合重复。因此,可以安全地跳过,不遗漏任何独特的三元组。
b. 找到和为零后跳过相同的 left
和 right
当找到一个和为零的三元组 [nums[i], nums[left], nums[right]]
后,我们添加这个三元组到结果列表中。然后,在移动 left
和 right
以寻找下一个可能的和为零的组合之前,我们跳过所有和当前 nums[left]
和 nums[right]
相同的元素。
- 对
left
的处理:增加left
指针,直到nums[left]
的下一个元素不同于当前nums[left]
。 - 对
right
的处理:减少right
指针,直到nums[right]
的前一个元素不同于当前nums[right]
。
这样做是因为,如果不跳过相同的 left
和 right
,那么即使 i
是不同的,新的 [nums[i], nums[left], nums[right]]
也只会是重复之前已经找到的三元组。
例子
考虑数组 [-1, -1, 0, 1, 1]
,排序后的数组中 -1
和 1
都重复出现。当第一次使用第一个 -1
作为 nums[i]
,并找到一个三元组 [-1, 0, 1]
后,如果我们不跳过第二个 -1
或者不在找到一个有效三元组后跳过相同的 left
和 right
,那么将会再次添加相同的三元组 [-1, 0, 1]
,从而导致结果中有重复。
完整示例解析:
假设我们有一个排序后的数组:[-4, -1, -1, 0, 1, 2, 2]
,我们要找出所有和为零的三元组。
初始步骤:
- 设定
i=0
,元素是-4
。 left
指向i+1
,即索引1
的位置,元素是-1
。right
指向数组的最后一个元素,索引6
,元素是2
。
查找过程:
- 计算和
-4 + (-1) + 2 = -3
,这个和小于零,所以我们需要一个更大的数来平衡,即将left
向右移动到索引2
。此时left
位置的元素仍是-1
。 - 重新计算和
-4 + (-1) + 2 = -3
,和仍小于零,再次将left
向右移动到索引3
,此时left
的元素是0
。 - 再次计算和
-4 + 0 + 2 = -2
,和仍小于零,移动left
到索引4
,元素是1
。 - 再次计算和
-4 + 1 + 2 = -1
,和仍小于零,继续移动left
,此时left
指向索引5
,元素仍是2
。 - 再次计算和
-4 + 2 + 2 = 0
,找到一个有效的三元组[-4, 2, 2]
。
避免重复的关键步骤:
找到三元组 [-4, 2, 2]
后,我们需要移动 left
和 right
来寻找下一个可能的三元组。重要的是,在移动这些指针前,我们需要确保跳过所有重复的值,避免重复添加相同的三元组:
- 从当前位置,
right
指针向左移动,跳过与当前right
值相同的所有元素。在这个例子中,right
已经在数组的末端,所以不需要移动。 left
指针向右移动,跳过与当前left
值相同的所有元素。但由于我们已经检查到末端,这个例子中不需要进一步移动。
代码解释:
while right > left and nums[right] == nums[right - 1]:
right -= 1
这一段循环确保如果 nums[right]
和它前一个元素 nums[right - 1]
相同,则 right
指针会继续向左移动,直到 nums[right]
的值改变。这样做是为了避免重复的三元组。例如,如果 nums[right]
重复出现,那么已经添加过的三元组再次添加就是重复的。
则移动左边的同理。
综上,本文的对于力扣15. 三数之和的Python3解答,仅仅是个人学习资料记录,也十分高兴我的见解可以帮助其他的正在做这个题目的同学,基础较差,仅仅是个人见解,大神勿喷,欢迎交流,谢谢!