当前位置 博文首页 > 向日葵的专属太阳：LeetCode15. 三数之和
题目来源：力扣（LeetCode）
题目描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例2：
输入：nums = []
输出：[]
示例3：
输入：nums = [0]
输出：[]
提示：
0 <= nums.length <= 3000-105 <= nums[i] <= 105解题思路：
特殊情况：nums 长度 length 小于 3，返回 []；对排序后 nums，若前三个值 >0 或后三个值 < 0，返回 [] 。
对数组进行排序。
遍历排序后数组：
nums[i] > 0：由于已排序，所以后面不可能有三个数加和等于 0，直接返回结果 rst。left = i + 1，右指针 right = length - 1，当 L < R 时，执行循环：nums[i] + nums[left] + nums[right] == 0 ，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L, R 移到下一位置，寻找新的解；若和大于 0，说明 nums[right] 太大，right 左移；若和小于 0，说明 nums[left] 太小，left 右移。class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
length = len(nums)
if length < 3:
return []
# 对nums排序（升序）
nums.sort()
if sum(nums[:3]) > 0 or sum(nums[-3:]) < 0:
return []
rst = []
for i in range(length - 2):
# 第一个数字已经>0，第二、三个数字只会比0大，故之后不存在满足条件的组合
if nums[i] > 0:
return rst
# 跳过重复的组合
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = length - 1
while left < right:
if nums[i] + nums[left] + nums[right] == 0:
# 保存结果
rst.append([nums[i], nums[left], nums[right]])
# 跳过重复的组合
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 跳过重复的组合
while left < right and nums[left] == nums[left + 1]:
left += 1
right -= 1
left += 1
# 三者结果小于0，left（第二个数字）右移（增大）
elif nums[i] + nums[left] + nums[right] < 0:
left += 1
# 三者结果大于0，right（第三个数字）左移（减小）
else:
right -= 1
return rst
