algorithm - Given an array of numbers, find out if 3 of them add up to 0

Question

Given an array of numbers, find out if 3 of them add up to 0.

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

Answer 1

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
  rev_iter = len(array) - 1
  while iter < rev_iter
    tmp = array[iter] + array[rev_iter] + array[i]
    if  tmp > 0
       rev_iter--
    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.