给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
时间: 2024-11-30 09:29:52 浏览: 10
这个问题是著名的“3Sum”问题,可以用哈希表(Hash Table)的数据结构和双指针法来解决。首先,我们需要遍历整个数组 `nums`,对于每一个元素 `num`,我们检查它与数组中其他元素之和是否等于 `-num`,这样就能找到所有和为 0 的三元组。
以下是基本的步骤:
1. 创建两个空集合,一个用于存储已遇到过的负数及其索引,另一个用于存储已遇到过的零元素及其索引。
2. 遍历数组,对于每个元素 `num`:
a. 计算 `target = -num`。
b. 使用两个指针,一个指向当前元素之后,另一个指向数组末尾。
c. 如果目标值已经在负数集合中,那么找到了一对,直接添加到结果集中,并更新负数集合的索引信息。
d. 否则,如果目标值在零集合中,说明我们已经有一对和为 0 的元素,现在只需要在剩余部分找到一个元素等于 `target` 即可。这时移动右指针(大的那个),跳过相同的元素。
e. 如果目标值不在集合中,将其加入负数集合并更新索引。
3. 返回结果集中的所有三元组。
注意,由于数组遍历过程中可能会有重复元素,所以在结果集中去除重复的组合是非常重要的一步。
以下是 Python 代码示例:
```python
def threeSum(nums):
nums.sort()
res = set()
n = len(nums)
for i in range(n-2):
if i > 0 and nums[i] == nums[i-1]: continue # 跳过重复元素
left, right = i+1, n-1
target = -nums[i]
while left < right:
sum_ = nums[left] + nums[right]
if sum_ < target:
left += 1
elif sum_ > target:
right -= 1
else:
res.add((nums[i], nums[left], nums[right]))
while left < right and nums[left] == nums[left+1]:
left += 1 # 移除重复元素
while left < right and nums[right] == nums[right-1]:
right -= 1 # 移除重复元素
left += 1, right -= 1
return list(res)
# 示例
print(threeSum([-1, 0, 1, 2, -1, -4])) # 输出 [(0, 0, 0), (-1, -1, 2)]
```
阅读全文