最原始的方法：
public class Solution {
public int threeSumClosest(int[] nums, int target) {
int len = nums.length;
if(len < 2) return 0;
int i = 0;
int sum = nums[0]+nums[1]+nums[2];
int minDiff = sum - target;
minDiff = minDiff < 0? (-1)*minDiff: minDiff;
if(minDiff == 0) return sum;
while(i < len - 2){
for(int j = i + 1; j < len-1; j++){
for(int k = j + 1; k < len; k++){
int temp = nums[i] + nums[j] + nums[k];
int diff = temp - target;
diff = diff < 0? (-1)*diff : diff;
if(diff == 0) return temp;
if(diff < minDiff){
minDiff = diff;
sum = temp;
}
}
}
i++;
}
return sum;
}
}
思维盲区，对原数组进行操作，其实只要题目没要求保留数组不变，我们可以先对数组排序（or other operation），这样数组不再是随机排列，查找起来就方便很多。Runtime 变为O（n^2）;
代码：
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int len = nums.length;
int i = 0;
int sum = nums[0]+nums[1]+nums[2];
int minDiff = sum - target;
minDiff = minDiff < 0? (-1)*minDiff: minDiff;
if(minDiff == 0) return sum;
while(i < len - 2){
int low = i + 1;
int high = len - 1;
while(low < high){
int temp = nums[i] + nums[low] + nums[high];
if(temp == target) return target;
while(low < high && temp < target){
int diff = temp - target;
diff = diff < 0? (-1)*diff : diff;
if(diff < minDiff){
minDiff = diff;
sum = temp;
}
low++;
temp = nums[i] + nums[low] + nums[high];
}
while(low < high && temp > target){
int diff = temp - target;
diff = diff < 0? (-1)*diff : diff;
if(diff < minDiff){
minDiff = diff;
sum = temp;
}
high--;
temp = nums[i] + nums[low] + nums[high];
}
}
i++;
}
return sum;
}
}
Jan 14 - 3 Sum Closest; Array; Two Pointer;
原文：http://www.cnblogs.com/5683yue/p/5132813.html