由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Leet Code, three sum closest
相关主题
请问这个3sumClosestLongest Consecutive Sequence 问题释疑
再来题目请教一个题目
找最近的点,这题咋解?Given a list of Points, output k Points closest to (0,0)怎么做
问一个面试题问几道面试题
First Missing Positive on Leetcode问一道算法题
我花了一个小时才调通过这个程序问一道题k Sum
题目来啦continuous subarray of closest sub
Ask a amazon question from careercup.Google电话面试题目
相关话题的讨论汇总
话题: sum话题: target话题: num话题: closest话题: int
进入JobHunting版参与讨论
1 (共1页)
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)
1 (共1页)
进入JobHunting版参与讨论
相关主题
Google电话面试题目First Missing Positive on Leetcode
问一道题我花了一个小时才调通过这个程序
再来一道简单的bit运算题题目来啦
Maximum Sum of Increasing SequenceAsk a amazon question from careercup.
请问这个3sumClosestLongest Consecutive Sequence 问题释疑
再来题目请教一个题目
找最近的点,这题咋解?Given a list of Points, output k Points closest to (0,0)怎么做
问一个面试题问几道面试题
相关话题的讨论汇总
话题: sum话题: target话题: num话题: closest话题: int