arrays - 查找未排序数组中是否存在元素 (x,y,z) 使得 x + y = z

Question

给定一个未排序的数组 A[1...n]。编写一个算法，如果 A 中存在三个元素 A[i]、A[j]、A[k] 则返回 true 使得 A[i]+ A[j] = A[k]，否则算法必须返回false(注意可能A[i] = A[j]是合法的)。所需时间为 O(n^2)。我想出了一个适用于 O(n^2 * log(n)) 的算法。我的算法对数组进行排序，然后对每对两个元素 x,y 使用二进制搜索来查找是否存在元素 x+y。是否有更快的解决方案需要 O(n^2)？

Answer 1

您可以先对数组进行排序 - O(nlogn)

然后它归结为在元素 A[0] .. A[k-1] 中为任何元素 找到 A[k] 的两个总和>A[k]

可以使用两个指针技术在 O(n) 中找到排序数组的两个和:

boolean searchSum( int k, int[] A ) {
      if ( k > A.length - 1 || k < 2 ) return false;
      i = 0, j = k-1

      while ( i < j ) { 

            if (A[i] + A[j] == A[k]) 
                return true; 
            else if (A[i] + A[j] < A[k]) 
                i++; 
            else
                j--; 
      } 

      return false; 
}

对于每个 k，它是 O(k-1)，总体复杂度应该是 O(n^2)。

你可以这样调用 searchSum:

boolean myMethod( int[] A ) {

   sort(A);
   for ( int i = A.length - 1; i >= 2; i-- ) {
      if ( searchSum( i, A ) ) {
        return true;
      }
   }

   return false;
}