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)
相关阅读
job talk 应该把所有project都涉及到吗一道求median的题bloomberg onsite 语言问题求教[合集] H4 pending, 可以拿到h1b receipt就工作吗？有木有人了解novartis in emeryville，数次求职无果，请支招！时隔1年半，重新来找工作~~~有没有不经过OPT从F1直接H1B的？Alien number问题不走Eb-1的话, 身份多久能拿到?Associate scientist到底是多高的职位？求blessing[合集] 求问面试时一道ethics的题目求bless。。。。。成了就把剩下的几个包子发完！！请问哪里能办OPT Extention？有谁面过box.net?求问，世界银行属于e-verify的机构吗？GATE Patni 这个公司怎么样hire 4-5 EE/CS junior or seniorA家 first phone interview博士毕业之前工作怎么操作