网站主机免费申请佣金高的推广平台

三数之和

问题描述

LeetCode 15.三数之和
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解决思路

这个问题可以通过先将数组排序，然后使用双指针来解决。具体解决步骤如下：

1. 首先对数组 nums 进行排序，以便后续双指针的操作。

2. 初始化一个空列表 res 用于存储符合条件的三元组。

3. 使用外层循环遍历数组 nums，将当前元素设为 nums[first]。

4. 在内层循环中，使用双指针 second 和 third 来寻找满足条件的三元组。second 从 first 的下一个位置开始，third 从数组的最后一个位置开始。

5. 在内层循环中，首先判断是否需要跳过重复的元素，即如果 second > first + 1 并且 nums[second] == nums[second-1]，则跳过当前元素。

6. 在内层循环中，使用 target 变量表示目标值，即 target = -nums[first]。

7. 使用 while 循环来不断调整 second 和 third 指针，使它们向中间靠拢，直到找到一个满足条件的三元组或者 second == third 时结束。

8. 如果找到一个满足条件的三元组，将其添加到结果列表 res 中。

9. 继续外层循环，重复上述步骤，直到遍历完整个数组。

10. 返回结果列表 res。

代码实现

以下是使用Python编写的代码，实现了上述解决思路，并添加了注释以解释每个步骤：

class Solution:def threeSum(self, nums):n = len(nums)nums.sort()  # 对数组进行排序res = []  # 存储结果的列表for first in range(n):if first > 0 and nums[first] == nums[first - 1]:  # 跳过重复的元素continuethird = n - 1  # 初始化第三个指针target = -nums[first]  # 计算目标值for second in range(first + 1, n):if second > first + 1 and nums[second] == nums[second - 1]:  # 跳过重复的元素continuewhile second < third and nums[second] + nums[third] > target:  # 调整第二个和第三个指针third -= 1if second == third:breakif nums[second] + nums[third] == target:  # 找到满足条件的三元组res.append([nums[first], nums[second], nums[third]])return res  # 返回结果列表

复杂度分析

• 时间复杂度: O(N^2)，其中N是数组nums的长度。

• 空间复杂度: O(log N)。我们忽略了存储答案的空间，额外的排序操作空间复杂度为O(log N)。但需要注意的是，由于我们修改了输入数组nums，在实际情况下可能不允许这种操作。因此，也可以将其看作是使用了一个额外的数组来存储nums的副本并进行排序，这样空间复杂度为O(N)。

结论

三数之和问题是一个经典的双指针问题，通过使用双指针方法，我们可以高效地找到满足条件的三元组。这个算法的时间复杂度和空间复杂度都在合理范围内，适用于大多数情况。希望这篇博客能够帮助你更好地理解和解决这个问题。