Problem
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
1
2
3
4
5Example:
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
给定n个数的数组以及一个整数target, 在数组内查找3个数a,b,c使得三者之和最接近target. 返回这三个数的和. 假设数组中一定存在一个解决方案.
Solution
Analysis
这种K-Sum题,解法类似: 排序+夹逼定理. 先对数组排序, 然后再循环k-2次循环, 内部进行夹逼, 时间复杂度为O(N ** K-1).
由于这里是求3Sum,但并不是等于,而是最接近. 所以至少需要两个变量:一个记录最终结果,一个记录和target之间的绝对值差距.通过循环求和,比较,更新结果变量和差距变量. 也可以只使用一个变量,result; 和target之间的差距每次重新计算, 然后对result更新.
Code
两个变量
1 | class Solution { |
一个变量
1 | class Solution { |