1 题目
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).
2 思路
好吧，过了好几个月没刷了，这个题做的很蛋疼，花了4、5个小时。首先是题目意思理解错误，然后再理解对了的情况下，思路又错了。不得不看别人答案。
这道题原来最好的解决方法都是o(n^2)。
既然要求时间复杂度是o(n^2)，那么思路就好办了。遍历所有的3个组合，看哪个距target最近就ok了。采用的方法是一个头指针、一个尾指针，一个current指针，详情，看代码。
3 代码
public int threeSumClosest(int[] nums, int target) { int sum = 0; if (nums.length <= 3) { for (int i : nums) { sum += i; } return sum; } Arrays.sort(nums); sum = nums[0]+nums[1]+nums[2]; int add = sum; for (int i = 0; i < nums.length - 2; i++) { int head = i+1; int end = nums.length-1; while(head < end){ add = nums[i] + nums[head] + nums[end]; if (add < target ) { head++; }else{ end--; } if (Math.abs(add-target) < Math.abs(sum-target)) { sum = add; } } } return sum; }
今后，尽量，两天一题。
原文：http://www.cnblogs.com/lingtingvfengsheng/p/4774886.html