描述
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
只需要返回三元组之和，无需返回三元组本身
在线评测地址：领扣题库官网
样例1
输入:[2,7,11,15],3
输出:20
解释:
2+7+11=20样例2
输入:[-1,2,1,-4],1
输出:2
解释:
-1+2+1=2解法思路
- 本题是57. 三数之和的扩展问题，不再要求恰好相等，而是找与target最接近的三数之和。
- 本题需要计算三数之和，如果用暴力枚举，时间复杂度会是O(n3)O(n3)。我们这里采用双指针的方法，来降低时间复杂度。首先将数组排序，然后固定一个数numbersi上用双指针来找与target最接近的三数之和nearest。
算法流程 - 第一步，对数组进行排序。只有将数组转化为有序数组，我们才方便移动双指针。
- 第二步，在数组numbers中遍历，每次固定numbers[i]作为第一个数
- 建立双指针left和right，初始化分别指向i + 1和len(numbers) - 1
- 求出此时的三数之和curr，如果curr和target恰好相等，我们可以直接返回target。
- 比较curr和nearest谁距离target更近，如果是curr，那么将nearest更新为target
- 判断curr和target的大小关系，如果curr > target，那么right左移；反之，left右移。继续第二步的过程，直到left >= right。
- 此外，当数组中有重复元素时，为了避免重复运算，在代码中添加了三处剪枝操作。当指针指向新的位置和旧的位置的值相等时，我们继续移动指针。
算法复杂度 - 时间复杂度
- 数组排序的时间复杂度为O(nlogn)O(nlogn)
- 遍历过程，固定值为 n 次，双指针为 n 次，时间复杂度为 O(n2))O(n2))
- 总时间复杂度：O(nlogn)+O(n2)=O(n2)O(nlogn)+O(n2)=O(n2)
- 空间复杂度为O（1），只需要常量空间。
class Solution: """ @param numbers: Give an array numbers of n integer @param target: An integer @return: return the sum of the three integers, the sum closest target. """ def threeSumClosest(self, numbers, target): nearest = float('inf') # step1: 首先对数组进行排序 numbers = sorted(numbers) # step2: 遍历 for i in range(len(numbers) - 2): # 剪枝1 if (i > 0 and numbers[i] == numbers[i - 1]): continue # 定义双指针 left = i + 1 right = len(numbers) - 1 # 双指针相向而行 while (left < right): # 此时的三数之和 curr = numbers[left] + numbers[right] + numbers[i] # 和恰好为target if curr == target: return target # 更新 nearest if abs(curr - target) < abs(nearest - target): nearest = curr # 移动双指针 if curr > target: right -= 1 # 剪枝2 while (right >= 0 and numbers[right] == numbers[right + 1]): right -= 1 else: left += 1 # 剪枝3 while (left < len(numbers) and numbers[left] == numbers[left - 1]): left += 1 return nearest
