LeetCode攀登之旅(9)
- 2019 年 10 月 5 日
- 筆記
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_list
2.最接近三数之和
【问题】
给定一个包括 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
