Give array of numbers, find out if 3 of them add up to 0

Question

Do it in N^2, how would one do this

Answer 1

put the negative of each number into a hash table or some other constant time lookup data structure. (n)

loop through the array getting each set of two numbers (n^2), and see if their sum is in the hash table.

Answer 2

O(n^2) solution without hash tables (because using hash tables is cheating :P). Here's the pseudocode:

Sort the array // O(nlogn)

for each i from 1 to len(array) - 1
  iter = i + 1
  reviter = len(array) - 1
  while iter < reviter
    tmp = array[iter] + array[reviter] + array[i]
    if  tmp > 0
       reviter--
    else if tmp < 0
       iter++
    else 
      return true
return false

Basically using a sorted array, for each number (target) in an array, you use two pointers, one starting from the front and one starting from the back of the array, check if the sum of the elements pointed to by the pointers is >, < or == to the target, and advance the pointers accordingly or return true if the target is found.

Answer 3

Not for credit or anything, but here is my python version of Charles Ma's solution. Very cool.

def find_sum_to_zero(arr):
    arr = sorted(arr)
    for i, target in enumerate(arr):
     lower, upper = 0, len(arr)-1
     while lower < i < upper:
      tmp = target + arr[lower] + arr[upper]
      if tmp > 0:
       upper -= 1
      elif tmp < 0:
       lower += 1
      else:
       yield arr[lower], target, arr[upper]
       lower += 1
       upper -= 1

if __name__ == '__main__':
    # Get a list of random integers with no duplicates
    from random import randint
    arr = list(set(randint(-200, 200) for _ in range(50)))
    for s in find_sum_to_zero(arr):
     print s