a*****t
发帖数: 30 | 1 The 3sum problem is defined as follows:
given a set S of n integers, dothere exist three elements {a, b, c} 2 S such
that a + b + c = 0?
This is a linear satisfiability problem. 3sum can be solved using a simple
algorithm with O(n^2) runtime (sort S, then test 3-tuples intelligently).
我不是特别清楚如何 "test 3-tuples intelligently" in O(n^2).
能给点意见吗？ 多谢 | g*****g
发帖数: 34805 | 2 I can think of a simple one.
hash the opposite of every number.
Now add every pair (C(N, 2)= O(N^2)) and check hash O(1)
such
【在 a*****t 的大作中提到】
: The 3sum problem is defined as follows:
: given a set S of n integers, dothere exist three elements {a, b, c} 2 S such
: that a + b + c = 0?
: This is a linear satisfiability problem. 3sum can be solved using a simple
: algorithm with O(n^2) runtime (sort S, then test 3-tuples intelligently).
: 我不是特别清楚如何 "test 3-tuples intelligently" in O(n^2).
: 能给点意见吗？ 多谢
| X****r
发帖数: 3557 | 3 No need to hash to find pairs of (a,b) from sets A and B respectively such
that
a + b == s in O(N+M) time, where the size of A is N and size of B is M, if
both
A and B are sorted and contain unique members. Just start from (i,j) = (1,m)
,
and increase i if a_i + b_j < s or decrease j if a_i + b_j > s.
【在 g*****g 的大作中提到】
: I can think of a simple one.
: hash the opposite of every number.
: Now add every pair (C(N, 2)= O(N^2)) and check hash O(1)
:
: such
| a*****t
发帖数: 30 | 4 Hash 方法不错。
感觉 Xentar 更简洁，漂亮些。
多谢！！ | c**a
发帖数: 316 | 5 Three sum?
funny title.
such
【在 a*****t 的大作中提到】
: The 3sum problem is defined as follows:
: given a set S of n integers, dothere exist three elements {a, b, c} 2 S such
: that a + b + c = 0?
: This is a linear satisfiability problem. 3sum can be solved using a simple
: algorithm with O(n^2) runtime (sort S, then test 3-tuples intelligently).
: 我不是特别清楚如何 "test 3-tuples intelligently" in O(n^2).
: 能给点意见吗？ 多谢
|
|
