0

Is there any better solution than the obvious O(n^3)? I can use one element multiple times so for an array {-1, 0, 2} there is a solution: (-1, -1, 2) or (0, 0, 0).

Martin Zynge
  • 9
  • 1
  • iterate all sum pairs then check if that sum * -1 is in your array. O(n^2) solution – juvian Nov 14 '18 at 18:44
  • @juvian isn't this log(n) * n^2 ? (log(n) because you search the array) – Gabriel Devillers Nov 14 '18 at 18:48
  • Possible duplicate of [O(NlogN) finding 3 numbers that have a sum of any arbitrary T in an array](https://stackoverflow.com/questions/1861516/onlogn-finding-3-numbers-that-have-a-sum-of-any-arbitrary-t-in-an-array) – Gabriel Devillers Nov 14 '18 at 18:54
  • This can be done in `O(n^2)`. You can find a similar question [here](https://stackoverflow.com/questions/53210351/find-if-there-are-elements-x-y-z-in-unsorted-array-so-that-x-y-z), but there the question was to see `x + y = z`, in your case `z` would be `-(x+y)`. – SomeDude Nov 14 '18 at 20:06
  • Not if you search with a hashtable – juvian Nov 14 '18 at 20:06

1 Answers1

0

The classic 3SUM problem can be solved in O(n^2). This can also be solved with O(n^2)

# assume arr is sorted and doesn't contain duplicates

out = []
s = set(arr)
for i in range(len(arr)):
    for j in range(i, len(arr)):
        a = - (arr[i] + arr[j])
        if a >= arr[j] and a in s:
            out.append((arr[i], arr[j], a))
Kevin He
  • 1,210
  • 8
  • 19