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 に答える