2

这是我在某处看到的一个面试问题并提出了这个问题：

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");
    }
}
4

1 回答 1

2

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

于 2012-12-10T22:34:22.413 回答