当前位置：首页 > news >正文

力扣15题. 三数之和

news 文章来源：https://blog.csdn.net/weixin_47337647/article/details/137797226 2024/10/29 1:20:57

题目：

给你一个整数数组 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，那么排序后的元素必定都大于0if 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 + 1right = len(nums) - 1while right > left:# 计算三元组的和sum_ = nums[i] + nums[left] + nums[right]if sum_ < 0:# 如果 sum_ 小于 0，表示需要更大的数来抵消负数，因此将 left 指针向右移动一位left += 1elif sum_ > 0:# 如果 sum_ 大于 0，表示需要更小的数来减小总和，因此将 right 指针向左移动一位right -= 1else:# 如果 sum_ 等于 0，将当前三元组 [nums[i], nums[left], nums[right]] # 加入到结果列表 resultresult.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 -= 1left += 1return 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解答，仅仅是个人学习资料记录，也十分高兴我的见解可以帮助其他的正在做这个题目的同学，基础较差，仅仅是个人见解，大神勿喷，欢迎交流，谢谢！

题目：