Leet Code, three sum closest - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Leet Code, three sum closest

Leet Code, three sum closest# JobHunting - 待字闺中

f*i2012-08-13 07:08

1 楼

3Sum Closest
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).
-----------------------------------------------
What is the most efficient solution, I can only think about an
O(n^2 logn)
Please suggest.

c*n2012-08-13 07:08

2 楼

This is my solution. I think it is O(n^2)
public int threeSumClosest(int[] num, int target) {

if (num==null || num.length<3)
return 0;

Arrays.sort(num);
int output=num[0]+num[1]+num[2];
for (int i=0; iint l=i+1;
int r=num.length-1;
while(lint sum=num[i]+num[l]+num[r];
if (sum==target){
return target;
}else if (sum>target){
if (Math.abs(sum-target)output=sum;
r--;
}else{
if (Math.abs(sum-target)output=sum;
l++;
}
}
}
return output;

}

h*o2012-08-13 07:08

3 楼

我做的跟 3sum 是一个复杂度 O(n^2); 做法也跟 3sum差不错。
1.先sort 数组S，O(nlgn);
2. 使用三个下标 i (当前下标) f(头下标) t(尾下标)
i 从0 到 n-1 遍历 // n 是数组长度
对于每一个i，设置 f = i+1, t = n-1,
计算 sum = S[i] + S[f] + S[t], 如果比之前的sum更接近，更新。
然后，如果sum 比target 小， f++，否则 t--
对于每一个 i ，以上操作循环至 f>= t, 所以每一个 i 要遍历数组一遍
最终，第2步的复杂度是 O(n^2)>O(nlgn), 所以这个算法复杂度也是O(n^2)