Java面试任务: Complete the Java method for a sorted array

Question

这个问题已经有答案了:

已关闭 11 年前。

Possible Duplicate:
Find a pair of elements from an array whose sum equals a given number

我最近遇到了以下 Java 面试问题。

目标是仅通过一次输入数组来完成方法任务。

我声称不可能一次性通过阵列来完成这项任务，但我遇到了通常的沉默、停顿，然后面试官宣布面试结束，但没有给我答案。

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

}

Answer 1

我不确定您正在寻找数组中的哪些值(“前两个”整数是什么意思？它们索引的最小总和？一个是最小的？任何两个恰好首先弹出的值？)，但是这个解决方案是 O(n)，需要一次传递，不使用额外的数据结构，并且仅使用一个额外的 int。它并不总是找到最接近的两个索引，也不总是找到“第一个”，无论这意味着什么。我相信它总会找到总和最小的两个(直到你们找到反例)。

如果你们发现任何错误，请告诉我:

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 :(");

    }  
}

您可以查看输出here .