algorithm - 给定一个数字数组，找出其中 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

基本上使用排序数组，对于数组中的每个数字(目标)，您使用两个指针，一个从数组的前面开始，一个从数组的后面开始，检查所指向的元素的总和是否pointers is >, < or == to the target, 并相应地推进指针，如果找到目标则返回 true。