LeetCode攀登之旅(9)
LeetCode攀登之旅(9)
公众号guangcity
发布于 2019-09-20 12:04:45
发布于 2019-09-20 12:04:45
LeetCode攀登之旅(9)
0.说在前面
1.三数之和
2.最接近三数之和
3.作者的话
0.说在前面
又到了我们刷题时间，每周二，周五更新LeetCode，有时一道，简单两道左右！
点击公众号右下角合作转载->联系我，即可加入我的个人微信，共同探讨交流，以及入交流群(记得备注入群)！
今天刷的为两道相关的题，分别是求三数之和与最接近的三数之和！
1.三数之和
【问题】
给定一个包含 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_list2.最接近三数之和
【问题】
给定一个包括 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本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录