Go over all pairs of numbers and store their sum(and also store which numbers give that sum). After that for each sum check if its negation is found among the sums you have. Using a hash you can reach quadratic complexity, using std::map, you will reach O(n^2*log(n))
.
EDIT: to make sure no number is used more than once it will better to store indices instead of the actual numbers for each sum. Also as a given sum may be formed by more than one pair, you will have to use a hash multimap. Having in mind the numbers are different for a sum X = a1 + a2
the sum -X
may be formed at most once using a1
and once using a2
so for a given sum X
you will have to iterate over at most 3 pairs giving -X
as sum. This is still constant.
Read full article from Quadratic algorithm for 4-SUM - Stack Overflow
No comments:
Post a Comment