由网友(人走茶亦凉)分享简介：鉴于数字数组，看看其中3人加起来为0。Given an array of numbers, find out if 3 of them add up to 0.做到这一点的N ^ 2，如何将一个做到这一点？Do it in N^2, how would one do this?推荐答案没有哈希表为O（n ^...

鉴于数字数组，看看其中3人加起来为0。

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

做到这一点的N ^ 2，如何将一个做到这一点？

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

推荐答案

没有哈希表为O（n ^ 2）解决方案（因为使用哈希表是一种欺骗行为：P）。这里的伪code：

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

基本上使用排序的数组，每个阵列中的，你用两个指针，从前面的一个开始，一个来自阵列背面起始号码（目标），检查元素的总和指向的三分球是>，＆LT;或==目标，并推进相应的指针或返回true，如果目标被发现。

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.