m*****y
发帖数: 120 | 1 Given 3 array of numbers (can be positive, or negative), get one from each
array to form a triplet:
1) find whether there is a triplet that add to 0.
2) find all the triplets that add to 0.
The 3 array have the same size (length).
Of course, N^3 will be the default answer.
Any better idea?
for example:
A: 3, -5, 9
B: -2, 4, 1
C: 2, -1, 7
Then 3(from A) + -2 (from B) + -1 (From C) is 0. | r*******y
发帖数: 1081 | 2 O(n^2)
【在 m*****y 的大作中提到】
: Given 3 array of numbers (can be positive, or negative), get one from each
: array to form a triplet:
: 1) find whether there is a triplet that add to 0.
: 2) find all the triplets that add to 0.
: The 3 array have the same size (length).
: Of course, N^3 will be the default answer.
: Any better idea?
: for example:
: A: 3, -5, 9
: B: -2, 4, 1
| j*******r
发帖数: 52 | 3 将BC中所有可能的加和hash -> O(n^2)
foreach v in A:
Hash.get(0-A) -> O(n) | c*******n
发帖数: 63 | 4 1.sort three array first --> nlgn
2.1 form the first two elements --> n^2
2.2 find the third element of triplet --> lgn (binary search)
or as justcoder said, hash the third array, then the searching will be
O(1)
==> O(n^2 * lgn) or O(n^2) | F**r
发帖数: 84 | 5 this is a variation of 3-sum problem, so complexity O(N^2)
【在 m*****y 的大作中提到】
: Given 3 array of numbers (can be positive, or negative), get one from each
: array to form a triplet:
: 1) find whether there is a triplet that add to 0.
: 2) find all the triplets that add to 0.
: The 3 array have the same size (length).
: Of course, N^3 will be the default answer.
: Any better idea?
: for example:
: A: 3, -5, 9
: B: -2, 4, 1
|
|
