FB的这道题怎么答？# JobHunting - 待字闺中
j*e
1 楼
看似combination sum的变种，其实因为有负数，情况就不一样了。
例如给你一个数组[-5, 5, 10], 之中的元素可以重复使用，找出这个数组是否包含3个
元素加起来为零的情况，返回T or F 即可
暴力DFS?
例如给你一个数组[-5, 5, 10], 之中的元素可以重复使用，找出这个数组是否包含3个
元素加起来为零的情况，返回T or F 即可
暴力DFS?
L*e
2 楼
3个元素不是3Sum吗？
m*0
3 楼
基本典型的3sum
num = [-5, 5, 10]
sort(num)
for (i=0; i
int a=i, b=len-1
while (a <= b)
if (num[a]+num[b] > 0-num[i]) b--;
else if ( < ) a++;
else return true;
}
return false;
O(n^2)
【在 j******e 的大作中提到】
: 看似combination sum的变种，其实因为有负数，情况就不一样了。
: 例如给你一个数组[-5, 5, 10], 之中的元素可以重复使用，找出这个数组是否包含3个
: 元素加起来为零的情况，返回T or F 即可
: 暴力DFS?
num = [-5, 5, 10]
sort(num)
for (i=0; i
int a=i, b=len-1
while (a <= b)
if (num[a]+num[b] > 0-num[i]) b--;
else if ( < ) a++;
else return true;
}
return false;
O(n^2)
【在 j******e 的大作中提到】
: 看似combination sum的变种，其实因为有负数，情况就不一样了。
: 例如给你一个数组[-5, 5, 10], 之中的元素可以重复使用，找出这个数组是否包含3个
: 元素加起来为零的情况，返回T or F 即可
: 暴力DFS?
j*e
4 楼
想复杂了，以为是可以选N个元素。原来是三个，汗。如此简单
【在 m******0 的大作中提到】
: 基本典型的3sum
: num = [-5, 5, 10]
: sort(num)
: for (i=0; i
: int a=i, b=len-1
: while (a <= b)
: if (num[a]+num[b] > 0-num[i]) b--;
: else if ( < ) a++;
: else return true;
【在 m******0 的大作中提到】
: 基本典型的3sum
: num = [-5, 5, 10]
: sort(num)
: for (i=0; i
: int a=i, b=len-1
: while (a <= b)
: if (num[a]+num[b] > 0-num[i]) b--;
: else if ( < ) a++;
: else return true;
b*5
5 楼
actually, it's DFS. The actual problem allowed duplicates, i think
【在 m******0 的大作中提到】
: 基本典型的3sum
: num = [-5, 5, 10]
: sort(num)
: for (i=0; i
: int a=i, b=len-1
: while (a <= b)
: if (num[a]+num[b] > 0-num[i]) b--;
: else if ( < ) a++;
: else return true;
【在 m******0 的大作中提到】
: 基本典型的3sum
: num = [-5, 5, 10]
: sort(num)
: for (i=0; i
: int a=i, b=len-1
: while (a <= b)
: if (num[a]+num[b] > 0-num[i]) b--;
: else if ( < ) a++;
: else return true;
m*3
6 楼
if the set does not have 0. you can use 3sum and the vector built as sorted.
[a1, a1, a2, a2, ..... an, an}
【在 b**********5 的大作中提到】
: actually, it's DFS. The actual problem allowed duplicates, i think
[a1, a1, a2, a2, ..... an, an}
【在 b**********5 的大作中提到】
: actually, it's DFS. The actual problem allowed duplicates, i think
m*0
7 楼
我的code已经考虑到了allow duplicate
DFS时间复杂度是C(N, 3) = O(n^3)，用3sum是O(n^2)
【在 b**********5 的大作中提到】
: actually, it's DFS. The actual problem allowed duplicates, i think
DFS时间复杂度是C(N, 3) = O(n^3)，用3sum是O(n^2)
【在 b**********5 的大作中提到】
: actually, it's DFS. The actual problem allowed duplicates, i think
b*5
8 楼
我面的时候， 原题不是说 if there's a 3 sum that sums to a target
而是好像是要 all 3 numbers that sums
而且， 给你的不是 interger array
而是好像是 telephone pad似得， interger 1 can corresponds to {a，b，c}，
integer 2 can correspond to {d ，e， f}
然后给你个target， 和list of integers with duplicates
你现在要输出 corresponding combination
比如 3sum 结果可以是 {1，1，2}， {1，1， 2} ， {0， 2， 2}
{1，1，2} 你就要输出 {a, a, d}, {b, a, d}, {c, a, d} etc
去年这里也有人发过这题的。。 还讨论过。。。
【在 m******0 的大作中提到】
: 我的code已经考虑到了allow duplicate
: DFS时间复杂度是C(N, 3) = O(n^3)，用3sum是O(n^2)
而是好像是要 all 3 numbers that sums
而且， 给你的不是 interger array
而是好像是 telephone pad似得， interger 1 can corresponds to {a，b，c}，
integer 2 can correspond to {d ，e， f}
然后给你个target， 和list of integers with duplicates
你现在要输出 corresponding combination
比如 3sum 结果可以是 {1，1，2}， {1，1， 2} ， {0， 2， 2}
{1，1，2} 你就要输出 {a, a, d}, {b, a, d}, {c, a, d} etc
去年这里也有人发过这题的。。 还讨论过。。。
【在 m******0 的大作中提到】
: 我的code已经考虑到了allow duplicate
: DFS时间复杂度是C(N, 3) = O(n^3)，用3sum是O(n^2)
相关阅读
求问Dell在Santa Clara的software development staff engineer职位前景如何？Onsite feedback question简历问题求讨论我也来求个祝福吧JP Morgan ETrading Analyst实习可以negotiate工资吗？招聘启事 (Java Developer)面google居然被要求用javascript做题了Direct Technology求助,怎么跟现在公司/老板谈matchH1B成绩单USCIS要求到底怎样？Amazon intern offer 只给了两周时间考虑，想继续等下家，可以和HR延期吗？有人最近做 Amazon的 online assessment 吗？回馈中国人. Zillow公司 帮内推.Linkedin 上的 recommend (转载)PhD申请opt问题第二波.....扫盲贴：给大家讲讲公司的political game 2[急问]博士能用level I工资申请H1B吗？还有export license?H1B/LCA申请有需要本人签名的地方吗？用于申请H1B的简历要写多详细？