0.说在前面
1.三数之和
2.最接近三数之和
3.作者的话
又到了我们刷题时间,每周二,周五更新LeetCode,有时一道,简单两道左右!
点击公众号右下角合作转载->联系我,即可加入我的个人微信,共同探讨交流,以及入交流群(记得备注入群)!
今天刷的为两道相关的题,分别是求三数之和与最接近的三数之和!
【问题】
给定一个包含 n 个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
【思路】
固定第一个元素:前面跟后面元素回归中心,根据与0的差距,确定是低位还是高位移动,这样便可以实现求解所有元素的三数之和!
注意一个关键点:去重思想!
之前少写了去重的几行代码,导致超时,然后参考了一下老表的去重思路,添加了
if i==0 or nums[i] > nums[i - 1]:
这行关键去重,然后编译通过,对于重复的数据我们不需要再次计算,这样有利于减少运算时间!
【实现】
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
s_list = []
length = len(nums)
for i in range(length):
if i==0 or nums[i] > nums[i - 1]:
low = i+1
high = length - 1
while low < high:
s = nums[i] + nums[low] + nums[high]
if s==0:
s_list.append([nums[i],nums[low],nums[high]])
low+=1
high-=1
while low < high and nums[low] == nums[low - 1]:
low += 1
while low < high and nums[high] == nums[high + 1]:
high -= 1
elif s<0:
low+=1
elif s>0:
high-=1
return s_list
【问题】
给定一个包括 n 个整数的数组 nums
和 一个目标值 target
。找出 nums
中的三个整数,使得它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
【思路】
定义一个最大常量表示最接近的结果值,然后在每次求得sum时候,同步更新当前的最接近结果值就可以了!
在求sum时,采用O(n^2)时间复杂度,空间复杂度为O(1)的算法。这道题的遍历思想跟上述那道题很像!由于比较简单,就不多阐述了。
【实现】
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
length = len(nums)
val = 0x7FFFFFFF
for i in range(length):
low = i + 1
high = length - 1
while low < high:
sum = nums[i] + nums[low] + nums[high]
result = abs(sum - target)
if result<val:
t = sum
val=result
if sum == target:
return t
elif sum < target:
low += 1
elif sum>target:
high -= 1
return t