# 15. 3Sum 三数之和

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：3sum, 三数之和，题解，leetcode, 力扣，Python, C++, Java

## # 题目描述：

Given an array `nums` of n integers, are there elements a, b, c in `nums` such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

``````Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
``````

## # 解题方法

### # 方法一：统计频率+双指针

``````class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
count = collections.Counter(nums)
values = count.keys()
values.sort()
print(values)
N = len(values)
l, r = 0, N - 1
res = list()
visited = set()
for l in range(N):
for r in range(l, N):
t = 0 - values[l] - values[r]
if t in count:
if (t == 0 and count[t] >= 3) \
or (((t == values[l] and t != values[r]) or (t == values[r] and t != values[l])) and count[t] >= 2) \
or (l == r and values[l] != t and count[values[l]] >= 2) \
or (t != values[l] and t != values[r] and l != r):
curlist = sorted([values[l], t, values[r]])
finger = "#".join(map(str, curlist))
if finger not in visited:
res.append(curlist)
return res
``````

### # 方法二：原数组排序+双指针

``````class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
N = len(nums)
nums.sort()
res = []
for t in range(N - 2):
if t > 0 and nums[t] == nums[t - 1]:
continue
i, j = t + 1, N - 1
while i < j:
_sum = nums[t] + nums[i] + nums[j]
if _sum == 0:
res.append([nums[t], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i - 1]:
i += 1
while i < j and nums[j] == nums[j + 1]:
j -= 1
elif _sum < 0:
i += 1
else:
j -= 1
return res
``````

## # 日期

2018 年 10 月 17 日 —— 今又重阳，战地黄花分外香