应用题-哈希表-三数之和（哈希表和双指针）
- 版权声明：本站原创文章，于2026-04-24，由 管理员 发表。
- 转载请注明： 应用题-哈希表-三数之和（哈希表和双指针） | CodeGarden
~~直接想当然的写，没有去重。错误写法。~~
```python
class Solution:
# 给你一个整数数组 nums ，
# 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
# 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
# 注意：答案中不可以包含重复的三元组。
# 3 <= nums.length <= 3000
def threeSum(self, nums: list[int]) -> list[list[int]]:
n = len( nums )
ans = []
for i in range( n ):
a = nums[ i ]
# 两数之和:找到 b + c = -a
c_set = set()
for j in range( i + 1, n ):
b = nums[ j ]
c = -a - b
if c in c_set: ans.append( [ a, b, c ] )
else: c_set.add( b )
return ans
```
**如何去重：详情看代码 去重还是很费劲的!!!**
```python
class Solution:
# 给你一个整数数组 nums ，
# 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
# 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
# 注意：答案中不可以包含重复的三元组。
# 3 <= nums.length <= 3000
def threeSum(self, nums: list[int]) -> list[list[int]]:
n = len( nums )
def qsort( l, r ):
if l >= r: return
pivot = nums[ l + ( r - l ) // 2 ]
i = l - 1
j = r + 1
while i < j:
i += 1
while nums[ i ] < pivot: i += 1
j -= 1
while nums[ j ] > pivot: j -= 1
if i < j: nums[ i ], nums[ j ] = nums[ j ], nums[ i ]
qsort( l, j )
qsort( j + 1, r )
qsort( 0, n - 1 )
# 现在nums是排序后的
ans = []
for i in range( n ):
a = nums[ i ]
if a > 0: break # 此时 a < b < c
if i > 0 and nums[ i - 1 ] == nums[ i ]: continue # 去重 相同的值会找到相同的b和c
# 两数之和:找到 b + c = -a
c_set = set()
j = i + 1
while j < n:
b = nums[ j ]
c = -a - b
if c in c_set:
ans.append( [ a, b, c ] )
# 去重 跳过重复的b 避免添加重复的三元组
while j + 1 < n and nums[ j + 1 ] == b: j += 1
else: c_set.add( b )
j += 1
return ans
```
**双指针 更加清晰**
```python
class Solution:
# 给你一个整数数组 nums ，
# 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
# 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
# 注意：答案中不可以包含重复的三元组。
# 3 <= nums.length <= 3000
def threeSum(self, nums: list[int]) -> list[list[int]]:
# 双指针
# 首先将数组排序，然后有一层for循环，i从下标0的地方开始，
# 同时定义下标j在i+1的位置上，定义下标k在数组结尾的位置上。
# 相当于 a = nums[i]，b = nums[j]，c = nums[k]
# 因为数组是排序的，
# 如果a + b + c > 0 说明此时三数之和大了，所以k就应该向左移动，才能让三数之和小一些。
# 如果a + b + c < 0 说明此时三数之和小了，所以j就应该向右移动，才能让三数之和大一些，
# 直到j与k相遇为止。
n = len( nums )
nums.sort()
ans = []
for i in range( n ):
a = nums[ i ]
if a > 0: break # a + b + c 必然大于0
if i > 0 and nums[ i - 1 ] == nums[ i ]: continue # 去重
j = i + 1
k = n - 1
while j < k:
b = nums[ j ]
c = nums[ k ]
if a + b + c > 0: k -= 1
elif a + b + c < 0: j += 1
else:
# 找到
ans.append( [ a, b, c ] )
# 去重
while j < k and nums[ j + 1 ] == b: j += 1
while j < k and nums[ k - 1 ] == c: k -= 1
j += 1
k -= 1
return ans
```