java - 查找给定排序数组中的任何两个数字是否与数组中的任何第三个数字相加的最有效方法是什么？

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))就像 Louis 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) 左右，但我无法立即找到任何方法。我会继续考虑更多，这是一个很好的问题。