f*********i
发帖数: 197 | 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******n
发帖数: 710 | 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; i
int l=i+1;
int r=num.length-1;
while(l
int 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********o
发帖数: 14 | 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) |
|
