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).题意就是说寻找三个数据之和距离target最近的，思路和上一道题3Sum完全一样，只是修改一下寻找的目标即可，也即对于3Sum，先确定一个数字，然后这个问题就退化成了2Sum的问题。针对2Sum，先对数组排序，然后使用双指针匹配可行解就可以解决。 代码如下：
import java.util.Arrays; public class Solution { int minLen=Integer.MAX_VALUE; int finsum=0; public int threeSumClosest(int[] nums, int target) { if(nums==null || nums.length<3) return 0; if(nums.length==3) return nums[0]+nums[1]+nums[2]; Arrays.sort(nums); for(int i=0;i<nums.length;i++) { //重复的数据就不在统计 if(i>=1 && nums[i]==nums[i-1]) continue; //System.out.println("Index: "+nums[i]); getRes(nums,i+1,nums[i],target); } return finsum; } private void getRes(int[] nums, int beg,int a,int target) { int i=beg,j=nums.length-1; while(i<j) { int sum=nums[i]+nums[j]+a; if(sum > target) { if(minLen > sum-target) { minLen=sum-target; finsum=sum; } j--; }else if(sum < target) { if(minLen > target-sum) { minLen=target-sum; finsum=sum; } i++; }else { minLen=target-sum; finsum=sum; break; } } } public static void main(String[] args) { Solution so=new Solution(); int []a={1,1,1,1}; System.out.println(so.threeSumClosest(a,3)); } }C++做法如下，主要就是直接设置一个比较即可。
代码如下：
#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; class Solution { public: int finalSum = 0; int minLen = numeric_limits<int>::max(); int threeSumClosest(vector<int>& nums, int target) { if (nums.size() < 3) return 0; else if (nums.size() == 3) return nums[0] + nums[1] + nums[2]; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { if (i >= 1 && nums[i] == nums[i - 1]) continue; dealWithTwoSum(nums, i + 1, nums[i],target); } return finalSum; } void dealWithTwoSum(vector<int>& nums, int beg, int now,int target) { int i = beg, j = nums.size() - 1; while (i < j) { int sum = nums[i] + nums[j] + now; if (sum > target) { if (minLen > sum - target) { minLen = sum - target; finalSum = sum; } j--; } else if (sum < target) { if (minLen > target - sum) { minLen = target - sum; finalSum = sum; } i++; } else { minLen = 0; finalSum = sum; break; } } } };