Given an array of numbers, find out if 3 of them add up to 0
First sort the array, then for each negative number (A) in the array, find two elements in the array adding up to -A. Finding 2 elements in a sorted array that add up to the given number takes O(n) time, so the entire time complexity is O(n^2).
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.
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
Much later:
def find_sum_to_zero(arr):
limits = 0, len(arr) - 1
arr = sorted(arr)
for i, target in enumerate(arr):
lower, upper = limits
while lower < i < upper:
values = (arr[lower], target, arr[upper])
tmp = sum(values)
if not tmp:
yield values
lower += tmp <= 0
upper -= tmp >= 0
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.