点击上方“Ahab杂货铺”，选择“置顶公众号”

技术分享第一时间送达！

---

NO.15 三数之和

原题：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

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

例，给定数组 nums=[-1,0,1,2,-1,-4]， 满足要求的三元组集合为： [  [-1, 0, 1],  [-1, -1, 2] ]

分析：

之前是两数之和【打卡贴】（No.001）从零开始刷LeetCode，现在是三数之和，那么四数之和还会远吗？固定两个数，然后找第三个数是否在列表之中，且按照符合题意的形式输出。遍历所有情况，之后判断第三个数是否在列表的切片之中。代码中都有注释，应该不难于理解。

# 存储结果列表
res_list = []
# 对nums列表进行排序，无返回值，
排序直接改变nums顺序
nums.sort()
for i in range(len(nums)):
# 如果排序后第一个数都大于0，则跳出循环，
不可能有为0的三数之和
   if nums[i] > 0:
break
# 排序后相邻两数如果相等，
则跳出当前循环继续下一次循环，
相同的数只需要计算一次
   if i > 0 and nums[i] == nums[i-1]:
continue
# 记录i的下一个位置
   j = i + 1
# 最后一个元素的位置
   k = len(nums) - 1
   while j < k:
# 判断三数之和是否为0
       if nums[j] + nums[k] == -nums[i]:
# 把结果加入数组中
           res_list.append([nums[i],
                 nums[j], nums[k]])
# 判断j相邻元素是否相等，有的话跳过这个
            while j < k and nums[j] == nums[j+1]:
j += 1
# 判断后面k的相邻元素是否相等，是的话跳过
            while j < k and nums[k] == nums[k-1]:
k -= 1
# 没有相等则j+1，k-1，缩小范围
            j += 1
            k -= 1
# 小于-nums[i]的话还能往后取
      elif nums[j] + nums[k] < -nums[i]:
j += 1
      else:
k -= 1
return res_list

再介绍一种大神解法：

tmp = dict()

for i in range(len(nums)):
tmp[nums[i]] = tmp.get(nums[i], 0) + 1l
   eft = sorted(filter(lambda x: x < 0, tmp))
right = sorted(filter(lambda x: x >= 0, tmp))

if 0 in tmp and tmp[0] > 2:
res = [[0, 0, 0]]
else:
res = []

for i in left:
for j in right:
mid = -i - j
if mid in tmp:
if mid in (i, j) and tmp[mid] > 1:
res.append([i, mid, j])
elif mid < i or mid > j:
res.append([i, mid, j])
return res

进群交流后台回复关键字: 进群

福利传送门：

勿忘初心

近期推荐阅读：

程序猿资料大汇总

LeetCode】打卡记录（NO.1-10）

---

欢迎您的点赞和分享

▲长按关注此公众号