Java面试任务:完成排序数组的Java方法

Question

可能重复： 从数组中找出其和等于给定数字的一对元素

最近，我收到了以下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

我不确定您要寻找的数组中有哪些值(“前两个”ints意味着什么？他们指数的最小和？一个是最小的？)，但是这个解决方案是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 :(");

    }  
}

您可以查看输出这里。

Answer 2

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

Answer 3

下面是一个使用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);
            }
        }
    }
}