3Sum Closest
Total Accepted: 38586 Total Submissions: 143446
Question Solution
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). Show Tags
分析：先对原始序列做排序（快速排序），在查找最相近的三元组集合，在确定了第一个元素之后，后两个元素并不是依次扫描而是分别选择头和尾数据，使得查找时间复杂度降到n^2
public class Solution {
void Sort(int[] dz, int s, int e){
if(s==e-1)
{
if(dz[s]>dz[e])
{
int mid=dz[s];
dz[s]=dz[e];
dz[e]=mid;
}
}
else if(s<e)
{
int cur=s;
int j=e;
while(cur!=j)
{
if(cur<j)
{
if(dz[cur]>dz[j])
{
int mid=dz[cur];
dz[cur]=dz[j];
dz[j]=mid;
mid=cur;
cur=j;
j=mid;
}
else
j--;
}
else
{
if(dz[cur]<dz[j])
{
int mid=dz[cur];
dz[cur]=dz[j];
dz[j]=mid;
mid=cur;
cur=j;
j=mid;
}
else
j++;
}
}
Sort(dz, s, cur-1);
Sort(dz, cur+1, e);
}
}
public int threeSumClosest(int[] nums, int target) {
if(nums.length<3)
return 0;
Sort(nums, 0, nums.length-1);
int min=Math.abs(nums[0]+nums[1]+nums[2]-target);
int a1=0;
int a2=1;
int a3=2;
for(int i=0;i<nums.length-2;i++)
{
int j=i+1;
int k=nums.length-1;
while(j<k)
{
if(nums[i]+nums[j]+nums[k]>target)
{
if(Math.abs(nums[i]+nums[j]+nums[k]-target)<min)
{
min=Math.abs(nums[i]+nums[j]+nums[k]-target);
a1=i;
a2=j;
a3=k;
}
k--;
}
else if(nums[i]+nums[j]+nums[k]<target)
{
if(Math.abs(nums[i]+nums[j]+nums[k]-target)<min)
{
min=Math.abs(nums[i]+nums[j]+nums[k]-target);
a1=i;
a2=j;
a3=k;
}
j++;
}
else
{
return nums[i]+nums[j]+nums[k];
}
}
}
return nums[a1]+nums[a2]+nums[a3];
}
}