【leetcode刷题】20T10-三数之和
木又同学2020年第10篇解题报告
leetcode第15题：三数之和
https://leetcode-cn.com/problems/3sum/
【题目】
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]【思路】
暴力解法，三层循环，判断三数相加是否为0；要想得到唯一的三元组，还需要再次判断。
当然可以优化，遇到时间复杂度太高的，一般可以先排个序。排序以后，即使是三层循环，第一个数大于0，由于后两个数均大于0，不可能三数之和等于0；同理，前两个数之和大于0，第三个数肯定大于0，三数之和也肯定不等于0。
再次优化，使用字典存储元素及该元素在数组中最后位置。这样，对于一组nums[p1]和nums[p2]，查找nums[p2+1:]是否存在-nums[p1]-nums[p2]只需要O(1)的复杂度，时间复杂度降为O(n^2)
本来以为OK了，但是每次判断结果res中是否存在某个三元组，需要O(m)的时间，导致一直通不过所有case。其实，由于nums已经排序，得到的nums[p1]，nums[p2]以及p2之后的-nums[p1]-nums[p3]肯定升序排列的。因此，只要保证nums[p1]和nums[p2]不同即可。
【代码】
python版本
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
if len(nums) < 3:
return res
nums.sort()
# 存储下标，降低查找的时间复杂度
d = {}
for i, n in enumerate(nums):
d[n] = i
for i in range(len(nums)-2):
# 重复元素
if i > 0 and nums[i] == nums[i-1]:
continue
# 最小的数大于0，其余的不用判断
if nums[i] > 0:
break
for j in range(i+1, len(nums)-1):
# nums[i] + nums[j] > 0，j后续元素都大于0，不用判断
if nums[i] + nums[j] > 0:
break
if j > i+1 and nums[j] == nums[j-1]:
continue
if d.get(-nums[i]-nums[j], -1) > j:
res.append([nums[i], nums[j], -nums[i]-nums[j]])
return res本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-01-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读