j******e
发帖数: 64 | 1 看似combination sum的变种，其实因为有负数，情况就不一样了。
例如给你一个数组[-5, 5, 10], 之中的元素可以重复使用，找出这个数组是否包含3个
元素加起来为零的情况，返回T or F 即可
暴力DFS? | L********e
发帖数: 159 | | m******0
发帖数: 222 | 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?
| j******e
发帖数: 64 | 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;
| b**********5
发帖数: 7881 | 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*****3
发帖数: 1462 | 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
| m******0
发帖数: 222 | 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
| b**********5
发帖数: 7881 | 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)
|
|
