给定一组数字,找出其中3个加起来为0

Question

给定一组数字,找出其中3个加起来为0.

在N ^ 2做,怎么会这样做？

Answer 1

没有哈希表的O(n ^ 2)解决方案(因为使用哈希表是作弊:P).这是伪代码:

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

基本上使用排序数组,对于数组中的每个数字(目标),使用两个指针,一个从前面开始,一个从数组后面开始,检查指针指向的元素之和是否> ,<或==到目标,并相应地推进指针,或者如果找到目标则返回true.

Answer 2

不是为了信用或任何东西,但这是我的Charles Ma的解决方案的python版本.很酷.

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

很久以后:

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

Answer 3

将每个数字的负数放入哈希表或其他一些恒定时间查找数据结构中.(n)的

循环遍历数组获取每组两个数字(n ^ 2),并查看它们的和是否在哈希表中.