15. 三数之和

描述

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

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

示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

思路

思路一

这种数值列表中有加减的题目,排序后可能会更加方便些。

固定两个数,将 target 设置为两个数之和的相反数,看 target 是否在列表中,若在,则为一个结果。

class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ret = []
# 数组题,其中有加减操作的,排序后会方便很多
nums.sort()
len_nums = len(nums) for i in range(len_nums - 1):
for j in range(i+1, len_nums):
# 固定下来两个数,如果另外一个数也在数组中,则为一个结果
if -(nums[i]+nums[j]) in nums[j+1:]:
a_ret = [nums[i], nums[j], -(nums[i]+nums[j])]
if a_ret not in ret:
ret.append(a_ret) return ret

但是这种方法有两层循环,果然报了 TLE(Time Limit Exceeded) 错误。

思路二

固定一个数,设置 target 为其他两个数之和的相反数,即 0 - 当前数,由两头向中间遍历数组,找到之和符合 target 的两个数即是一个结果。

class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ret = []
nums.sort() for i in range(0, len(nums)):
# 若存在相同数,跳过以减少计算
if i > 0 and nums[i] == nums[i-1]:
continue target = 0 - nums[i]
start, end = i+1, len(nums)-1 while start < end:
# 头尾之和大于目标值,尾向前移一位
if nums[start] + nums[end] > target:
end -= 1
# 头尾之和小于目标值,头向后移一位
elif nums[start] + nums[end] < target:
start += 1
# 头尾之和等于目标值,是一个结果,添加进去
# 头尾都移动一位
else:
ret.append([nums[i], nums[start], nums[end]])
start += 1
end -= 1
# 若移动后有重复值,继续移动
while start < end and nums[start] == nums[start-1]:
start += 1
while start < end and nums[end] == nums[end+1]:
end -= 1 return ret

GitHub地址:https://github.com/protea-ban/LeetCode

LeetCode15. 三数之和-LMLPHP

05-11 13:04