题目描述
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
思路
排序 + 双指针
由于输入的顺序与三元组的顺序无关,因此改变数在数组中的位置并无关紧要。对数组先排序再处理极大方便了解题。
需要注意的是,题目不允许出现重复解。因此在每一层枚举时要注意去除重复元素。
代码由外循环和两个指针组成,对应的数分别为nums[i],nums[j],nums[k],
- 外层循环,若nums[i]>0,则必定不可能有nums[i]+nums[j]+nums[k]=0,直接结束循环。
- 两个指针j,k从i+1,len(nums)-1开始变化。当 j<k 时,执行循环:
case1: 当nums[i]+nums[j]+nums[k]=0时则加入列表中,指针移动,直到元素改变后结束移动指针,再寻找新的解。
case2: 若和大于0,则说明当前nums[k] 太大, k左移
case3: 若和小于0,则说明当前nums[j] 太小,j右移
代码
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n=len(nums)
# 排序
nums.sort()
# 记录结果
res=[]
for i in range(n):
# 当三个数中最小的数都大于0了,往后肯定找不到符合答案的值了
if(nums[i]>0):
return res
# 排除重复的元素
if(i>0 and nums[i]==nums[i-1]):
continue
j=i+1
k=n-1
while(j<k):
if(nums[i]+nums[j]+nums[k]==0):
# 满足条件,加入答案列表
res.append([nums[i],nums[j],nums[k]])
# 排除重复的元素(找到第一个比nums[j]大的数)
while(j<k and nums[j]==nums[j+1]):
j=j+1
# 排除重复的元素(找到第一个比nums[k]小的数)
while(j<k and nums[k]==nums[k-1]):
k=k-1
j=j+1
k=k-1
# 和大于0,nums[k]太大了
elif(nums[i]+nums[j]+nums[k]>0):
k=k-1
# 和小于0,nums[j]太大了
else:
j=j+1
return res
标签:15,nums,三数,示例,List,三元组,res,100,指针
From: https://www.cnblogs.com/anamzingclown/p/17559399.html