氷泠

# 1 题目

leetcode第16题，给定一个数组与一个目标数，找出数组中其中的三个数，这三个数的和要与目标数最接近。

# 2 暴力

``````int temp = nums[0]+nums[1]+nums[2];
for(int i=0;i<nums.length;++i)
for(int j=i+1;j<nums.length;++j)
for(int k=j+1;k<nums.length;++k)
{
int temp1 = nums[i]+nums[j]+nums[k];
if(Math.abs(temp-target) > Math.abs(temp1-target))
{
temp = temp1;
if(temp == target)
return target;
}
}
return temp;
``````

# 3 O(n2)

``````Arrays.sort(nums);
int t1 = nums[0]+nums[1]+nums[2];
for(int i=0;i<nums.length-2;++i)
{
int left = i+1;
int right = nums.length-1;

while(left < right)
{
int t2 = nums[i]+nums[left]+nums[right];
if(t2 == target)
return target;
else if(t2 > target)
--right;
else
++left;
if(abs(t1-target) > abs(t2-target))
{
t1 = t2;
}
}
}
return t1;
``````

# 4 冲击2ms

## 4.1 手写快排

（原理就不多说了，手写快排还是稍微有那么一点难度的...）

``````public void qs(int [] nums,int l,int r)
{
if(l < r-1)
{
int t = l;
int ll = l+1;
int rr = r-1;
int temp;
while(true)
{
while(t < rr && nums[t] < nums[rr])
--rr;
if(t < rr)
{
temp = nums[rr];
nums[rr] = nums[t];
nums[t] = temp;
t = rr--;
}
else
break;
while(ll < t && nums[ll] < nums[t])
++ll;
if(ll < t)
{
temp = nums[ll];
nums[ll] = nums[t];
nums[t] = temp;
t = ll++;
}
else
break;
}
qs(nums,l,t);
qs(nums,t+1,r);
}
}
``````

``````while(ll < rr && ...)
``````

``````while(t < rr && ...)
while(ll < t && ...)
``````

## 4.2 最大最小剪枝

``````int left = i+1;
int right = nums.length-1;
if(left < right)
{
int min = nums[i] + nums[left] + nums[left+1];
if(min > target)
{
if(abs(min - target) < abs(t1 - target))
t1 = min;
continue;
}
}

int max = nums[i] + nums[right] + nums[right-1];
if(max < target)
{
if(abs(max - target) < abs(t1 - target))
t1 = max;
continue;
}
``````

# 5 源码

github

### 评论(0)

Leecode N个数的和合集【1、15、16、18、167、454、923】

2019/07/13
0
0

lancel0t
2018/04/08
0
0
Lintcode59 3Sum Closest 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. Notice:You ma......

Winnielyn
2018/06/26
0
0

2018/01/17
0
0
SDL系列讲解（十） 按键处理流程

SDL系列讲解（一） 简介 SDL系列讲解（二） 环境搭建 SDL系列讲解（三） 工具安装 SDL是什么，能干什么，为什么我们要学习它？ SDL系列讲解（四） demo讲解 SDL系列讲解（五） 调试c代码 SD...

2017/10/28
0
0

16534163822
24分钟前
16
0

16566493077
25分钟前
35
0

16534163727
25分钟前
25
0

17035270196
26分钟前
18
0

17035270010
26分钟前
29
0