天地做网站,网站开发制作公司名称,营销策划公司品牌,建网站 北京题目#xff1a;
给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意#xff1a;答案中不可以包含重复…题目
给你一个整数数组 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]我们要找出所有和为零的三元组。
初始步骤
设定 i0元素是 -4。left 指向 i1即索引 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解答仅仅是个人学习资料记录也十分高兴我的见解可以帮助其他的正在做这个题目的同学基础较差仅仅是个人见解大神勿喷欢迎交流谢谢
