15. 三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
暴力, 三重遍历
import copy
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
for x in nums:
xnum = copy.deepcopy(nums)
xnum.remove(x)
for y in xnum:
ynum = copy.deepcopy(xnum)
ynum.remove(y)
for z in ynum:
if x + y + z == 0:
if [x,y,z] in res or [x,z,y] in res or [y,x,z] in res or [y,z,x] in res or [z,x,y] in res or [z,y,x] in res:
pass
else:
res.append([x,y,z])
return res
双指针法
遍历排序后数组:
- 若 nums[i]>0:
因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。- 对于重复元素:
跳过,避免出现重复解
令左指针 L=i+1,右指针 R=n-1,当 L<R时,执行循环:
当 nums[i]+nums[L]+nums[R]==0,执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,R 移到下一位置,寻找新的解
- 若和大于 0,说明 nums[R] 太大,R 左移
- 若和小于 0,说明 nums[L] 太小,L 右移
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
if n < 3 or not nums:
return []
for i in range(n):
if(nums[i] > 0):
return res
if(i>0 and nums[i] == nums[i-1]):
continue
L = i + 1
R = n - 1
while L < R:
if nums[i]+nums[L]+nums[R] == 0:
res.append([nums[i],nums[L],nums[R]])
while L<R and nums[L] == nums[L+1]:
L += 1
while(L<R and nums[R] == nums[R-1]):
R -= 1
L += 1
R -= 1
elif nums[i]+nums[L]+nums[R] > 0:
R -= 1
else:
L += 1
return res
16. 最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
nums = [-1,2,1,-4], target = 1.
与 target 最接近的三个数的和为 2.
-1 + 2 + 1 = 2
对 nums 排序
双指针法不断计算 sums 和 target 比较:
如果一致直接返回。
如果差值比之前存储的小就替换。
sums 比 target 小,左指针右移,增大左值
sums 比 target 大,右指针左移,减小右值
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
if not sum or n<3:
return []
nums.sort()
res = float('inf')
for i in range(n):
if i>0 and nums[i] == nums[i-1]:
continue
L = i+1
R = n-1
while L<R:
cur_sum = nums[i] + nums[L] + nums[R]
diff = cur_sum - target
if diff == 0:
return target
if abs(diff) < abs(res-target):
res = cur_sum
if diff < 0:
L += 1
while L<R and nums[L] == nums[L-1]:
L+=1
else:
R -= 1
while L<R and nums[R] == nums[R+1]:
R-=1
return res
网友评论