什么是最有效的方法来查找给定排序数组中的任何两个数字是否合计到数组中的第三个数字？

Question

这是我看到的地方，并与此想出了一个面试问题：

import java.util.Random; 
import java.util.Arrays; 
class SumTwo 
{ 
    public static void main(String arg[]) 
    { 
     Random r=new Random(); 

     int arr[]=new int[5]; 
     for(int i=0;i<arr.length;i++) 
     { 
      arr[i]=r.nextInt(20); 
     } 
     Arrays.sort(arr); 
     printArr(arr); 
     System.out.println(checkSum(arr)); 

    } 

    public static boolean checkSum(int[] arr) 
    { 
     for(int i=2;i<arr.length;i++) 
     { 
      if(check(arr,0,i-1,arr[i])) 
       return true; 
     } 
     return false; 
    } 


    public static boolean check(int[] arr, int st, int en, int sum) 
    { 

     int add=0; 
     while(st<en) 
     { 
      add=arr[st]+arr[en]; 
      if(add==sum) 
       return true; 
      else if(add>sum) 
       en--; 
      else 
       st++; 
     } 
     return false; 
    } 

    public static void printArr(int[] arr) 
    { 
     System.out.println("\n"); 
     for(int i=0;i<arr.length;i++) 
      System.out.print(" "+arr[i]); 
     System.out.println("\n"); 
    } 
} 

Answer 1

嗯，你是O（n^3）。 （编辑：我误读它，你是正确的，你的是O（n^2））像路易Wasserman说，有一个简单的算法O（n^2 log n），这里是一个O（n^2）使用一点点额外的内存：

public static boolean checkSum(int[] arr) { 
    HashSet<Integer> set = new HashSet<Integer>(); 
    for (int n : arr) { 
     set.add(n); 
    } 

    for (int i = 0; i < arr.length; i++) { 
     for (int j = i + 1; j < arr.length; j++) { 
      if (set.contains(arr[i] + arr[j])) return true; 
     } 
    } 
    return false; 
} 

可能需要为包含零的阵列，根据问题定义的特殊情况下，但这个想法是存在的。直观地说，看起来可能有一种巧妙的方式来做到这一点，即O（n log n）左右，但我不能立即找到任何东西。我会继续考虑一下，这是一个很好的问题。