1

重複の可能性:
合計が指定された数値に等しい配列から要素のペアを見つける

私は最近、次の Java インタビューの質問を受けました。

目標は、入力配列を 1 回パスするだけでメソッド タスクを完了することです。

私は、アレイを 1 回通過するだけではこのタスクを完了することはできないと主張しましたが、私はいつものように沈黙し、一時停止し、インタビュアーはインタビューが終了したと宣言しましたが、答えはありませんでした。 

public class SortedArrayOps {  
    public SortedArrayOps() {  

    }  

//    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.  
//  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.  
static void PrintIntSumValues(int Sum, int sortedInts[]) {  
//        need to test to see if the Sum value is contained in the array sortedInts. And, if not do nothing.  
    for(int i=0; i<sortedInts.length; i++) {  
//            ... do some work: algebra and logic ...  
//            System.out.println sortedInts[i]+sortedInts[?] sums to Sum.  
    }  
}  

public static void main(String[] args) {  
    final int[] sortedArray = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
    PrintIntSumValues(48, sortedArray);  
}

}

4

5 に答える 5

1

探している配列の値がわかりません (「最初の 2 つの」int はどういう意味ですか? それらのインデックスの最小合計? 1 つが最小ですか? たまたま最初にポップアウトする 2 つですか?)、しかし、この解決策は O( n)、1 つのパスを取り、追加のデータ構造を使用せず、追加の int を 1 つだけ使用します。最も近い 2 つのインデックスが常に見つかるとは限りません。また、それが何を意味するにせよ、常に「最初の」インデックスが見つかるとは限りません。合計が最小の2つが常に見つかると思います（反例が見つかるまで）。

バグを見つけたら教えてください:

class Test {

    public static void main(String[] args) {  
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        PrintIntSumValues(6, sortedArray);

        sortedArray = new int[] {1, 2,3, 12, 23423};
        PrintIntSumValues(15, sortedArray);


        sortedArray = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        PrintIntSumValues(100, sortedArray);

        sortedArray = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
        PrintIntSumValues(48, sortedArray);  
    }

    //    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.  
    //  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.  
    static void PrintIntSumValues(int Sum, int sortedInts[]) {  
        // need to test to see if the Sum value is contained in the array sortedInts. And, if not do nothing.  
        int offset = sortedInts.length-1;

        for(int i=0; i<sortedInts.length; i++) {  
            //            ... do some work: algebra and logic ...   
            if ((sortedInts[i] + sortedInts[offset]) == Sum){
                System.out.println("sortedInts[" + i + "]+sortedInts[" + offset + "] sums to " + Sum + ".");
                return;
            } else {
                int remaining = Sum - sortedInts[i];
                if (remaining < sortedInts[i] ){
                    // We need something before i
                    if (remaining < sortedInts[offset]) {
                        // Even before offset
                        offset = 0 + (offset - 0)/2;
                    } else {
                        // Between offset and i
                        offset = offset + (i - offset)/2;
                    }
                } else {
                    // We need something after i
                    if (remaining < sortedInts[offset]) {
                        // But before offset
                        offset = i + (offset - i)/2;
                    } else {
                        // Even after offset
                        offset = offset + (sortedInts.length - offset)/2;
                    }
                }
            }
        }  
        System.out.println("There was no sum :(");

    }  
}

ここで出力を表示できます。

于 2012-07-31T03:50:00.183 に答える
0

HashMapこれが：を使用した完全なソリューションです。

import java.util.HashMap;

public class Test
{
    public static void main(String[] args)
    {
        final int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int sum = 6;

        printSum(sum, sortedArray);
    }

    private static void printSum(int sum, int[] sortedArray)
    {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int index = 0; index < sortedArray.length; index++)
        {
            int currentNumber = sortedArray[index];
            int remainder = sum - currentNumber;

            if (map.containsKey(remainder))
            {
                System.out.println(String.format("%d + %d = %d", currentNumber, remainder, sum));

                break;
            }
            else
            {
                map.put(currentNumber, index);
            }
        }
    }
}
于 2012-07-31T02:49:46.203 に答える
0

これはうまくいくはずです。2 つのポインターがあり、データを 1 回だけ通過します。

j = sortedInts.length - 1;
for(int i=0; i<sortedInts.length && j>=i; i++) {  
    sx = sortedInts[i];
    while (sx + sortedInts[j] > Sum)
        j++;
    if (sx + sortedInts[j] == Sum)
        ...
}
于 2012-07-31T10:59:16.940 に答える
0

java.util.HashMap をインポートします。

            public class SortedArrayOps {

                public SortedArrayOps() {
                }

            //    Print at the system out the first two ints found in the sorted array: sortedInts[] whose sum is equal to Sum in a single pass over the array sortedInts[] with no 0 value allowed.
            //  i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to be found to complete the task.
            static void PrintIntSumValues(int Sum, int sortedInts[]) {
                HashMap<Integer, Boolean> pool= new HashMap<Integer, Boolean> ();
                for(int i=0; i<sortedInts.length; i++) {
                    int current = sortedInts[i];
                    int target = Sum - current;
                    if (pool.containsKey(target)) {
                        System.out.println(String.format("%d and %d sum to %d", current, target, Sum));
                        break;
                    }
                    else {
                        pool.put(current, Boolean.TRUE);
                    }
                }
            }

            public static void main(String[] args) {
                final int[] sortedArray = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50};
                PrintIntSumValues(48, sortedArray);
            }
            }
于 2012-07-31T02:31:45.127 に答える
-2

値の配列は固有であるため、ソリューションは次のように単純化できます。

public class SortedArrayOps {
public SortedArrayOps() {

}

// Print at the system out the first two ints found in the sorted array:
// sortedInts[] whose sum is equal to Sum in a single pass over the array
// sortedInts[] with no 0 value allowed.
// i.e. sortedInts[i] + sortedInts[?] = Sum where ? is the target index to
// be found to complete the task.
static void PrintIntSumValues(int Sum, int sortedInts[]) {
    // need to test to see if the Sum value is contained in the array
    // sortedInts. And, if not do nothing.
    for (int i = 0; i < sortedInts.length; i++) {
        // ... do some work: algebra and logic ...
        // System.out.println sortedInts[i]+sortedInts[?] sums to Sum.
        int remainder = Sum - sortedInts[i];
        if( remainder <= sortedInts.length && remainder>0 && remainder!=sortedInts[i]) {
            System.out.print(String.format("%d + %d = %d", sortedInts[i], sortedInts[remainder-1], Sum));
            break;
        }
    }
}

public static void main(String[] args) {
    final int[] sortedArray = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
            14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
            30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45,
            46, 47, 48, 49, 50 };
    PrintIntSumValues(48, sortedArray);
}

}

于 2012-07-31T04:27:03.327 に答える