蜗牛慢慢爬 LeetCode 16. 3Sum Closest [Difficulty: Medium]

题目

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

翻译

和 3sum 那道题大同小异... 传送门
只不过这次不再是求和为0的三个数也不是返回所有解，而是求出离target最近的三个数的和并返回

Hints

Related Topics: Array, Two Pointers

代码

Java

class Solution {
public int threeSumClosest(int[] nums, int target) {
int result = nums[0]+nums[1]+nums[nums.length-1];
        Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++){
int l = i+1, r = nums.length-1;
while(l<r){
int s = nums[i]+nums[l]+nums[r];
if(s>target)    
                r--;
else
                l++;
if(Math.abs(target-s)<Math.abs(target-result))
                result = s;
            }
        }
return result;
    }
}

Python

class Solution(object):
def threeSumClosest(self, nums, target):
        nums.sort()
        closest = nums[0]+nums[1]+nums[len(nums)-1]
if len(nums)<3: return

for i in range(0,len(nums)-2):
            l, r = i+1, len(nums)-1
while l<r:
                s = nums[i]+nums[l]+nums[r]
if abs(target-s)<=abs(target-closest):
                    closest = s
if s<target:
                    l+=1
elif s>target:
                    r-=1
else:
return target
return closest