转载

如何查找总和等于给定数字的整数数组中的所有对

在任何编程面试中，练习编码问题都非常重要。你应该尽量使用数组，链表和字符串这样的数据结构来清除任何编程访问。这是一个通过编码学习的漫长过程，而这正是这些小编码问题所帮助的所在。现在，我们将从阵列中看另一个有趣的编程问题;编写一个程序来查找总和等于给定数字的所有整数对。例如，如果输入整数数组是{2,6,3,9,11}并且给定的和是9，则输出应为{6,3}。听起来很简单？也许，但这个问题曾出现在亚马逊，微软，Facebook以及其他五家科技公司过去的技术面试中。很多人可能已经听说过这个问题，你们中的一些人可能已经知道了这个问题的解决方案，但仅仅知道答案是不够的。在编程面试中，除了正确的解决方案外，许多事情都很重要。例如，候选人是否可以提出正确的问题。因此，在直接进行编码之前，请花一两秒钟来思考问题并清除您可能遇到的任何疑问。例如，您可以根据上面给出的问题陈述提出以下问题：

数组只包含正数或负数吗？

如果同一对重复两次，我们应该每次都打印一次吗？

是否可以接受对的反转，例如如果给定的和是5，我们可以打印（4,1）和（1,4）。

我们是否只需打印不同的一对？（3,3）是有效的一对，是否为6？

阵列有多大？

许多程序员不敢提问而是他们喜欢假设，但在编程面试期间，恕我直言，提问相对更好。首先，它表明你没有抢救答案，其次表明你有能力思考问题，这是任何专业程序员的一个非常重要的品质。现在让我们回到问题，为简单起见，我们可以假设我们只需要根据它们的出现打印一对或两次整数，但是对必须是不同的，（2,2）或（3,3）不是有效的一对。

求数组中和为给定数的整数对的三种解法：

我想到的第一个解决办法是我们的朋友蛮力，天真而热诚。从数组中取出一个数字，然后循环遍历数组和输出对，这些对等于给定的和。对第一个数组中的所有数字都这样做，如下面的Java程序所示：

<b>import</b> java.util.Arrays;

<font><i>/**
 * Java Program to find pairs on integer array whose sum is equal to k
 * 
 * @author WINDOWS 8
 */</i></font><font>
<b>public</b> <b>class</b> ProblemInArray{

    <b>public</b> <b>static</b> <b>void</b> main(String args) {
        <b>int</b> numbers = { 2, 4, 3, 5, 7, 8, 9 };
        <b>int</b> numbersWithDuplicates = { 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 };
        prettyPrint(numbers, 7);
        prettyPrint(numbersWithDuplicates, 7);
    }

    </font><font><i>/**
     * Prints all pair of integer values from given array whose sum is is equal to given number.
     * complexity of this solution is O(n^2)
     */</i></font><font>
    <b>public</b> <b>static</b> <b>void</b> pr<b>int</b>Pairs(<b>int</b> array, <b>int</b> sum) {

        <b>for</b> (<b>int</b> i = 0; i < array.length; i++) {
            <b>int</b> first = array[i];
            <b>for</b> (<b>int</b> j = i + 1; j < array.length; j++) {
                <b>int</b> second = array[j];

                <b>if</b> ((first + second) == sum) {
                    System.out.printf(</font><font>"(%d, %d) %n"</font><font>, first, second);
                }
            }

        }
    }
    </font><font><i>/**
     * Utility method to print input and output for better explanation.
     */</i></font><font>
    <b>public</b> <b>static</b> <b>void</b> prettyPr<b>int</b>(<b>int</b> givenArray, <b>int</b> givenSum){
        System.out.println(</font><font>"Given array : "</font><font> + Arrays.toString(givenArray));
        System.out.println(</font><font>"Given sum : "</font><font> + givenSum);
        System.out.println(</font><font>"Integer numbers, whose sum is equal to value : "</font><font> + givenSum);
        printPairs(givenArray, givenSum);
    }

}

Output:
Given sum : 7
Integer numbers, whose sum is equal to value : 7
(2, 5) 
(4, 3) 
Given array : [2, 4, 3, 5, 6, -2, 4, 7, 8, 9]
Given sum : 7
Integer numbers, whose sum is equal to value : 7
(2, 5) 
(4, 3) 
(3, 4) 
(-2, 9) [/i]
</font>

这个解决方案是正确的，但它的时间复杂度非常高，O（n^2），这意味着面试官一定会要求你改进你的答案，并提出复杂度为O（1）、O（n）或O（nlog（n））的解决方案。所以，让我们更深入地研究，以改进这个答案。为了在一个求和等于给定值的数组中找到两个数字，我们可能不需要对每个数字进行比较。我们在这里可以做的是将所有数字存储在哈希表中，并检查它是否在一对中包含第二个值。例如，如果给定的和是4，成对的一个数是3，那么另一个数必须是1或-7。您还记得我们问的第一个问题吗？如果数组只包含正数，那么我们不需要在map中检查负值。该解决方案如何优于前一个解决方案？这将需要较少的比较。只有n可以迭代数组并在集合中插入值，因为在哈希表中，add（）和contains（）都是0（1）操作。所以解决方案的总复杂度是O（n）。这里是一个Java程序，它找到数组中的一对值，其值等于哈希表或集合的k。在这个程序中，我们还编写了在Java中给定范围内生成随机数的实用方法。您可以使用此方法对随机输入进行测试。顺便说一下，随机数只适合演示，不要在单元测试中使用它们。从printpairsusingset（）方法可以学到的另一个好处是预验证，检查输入是否有效，以便进一步进行。

<b>import</b> java.util.Arrays;
<b>import</b> java.util.HashSet;
<b>import</b> java.util.Set;

<font><i>/**
 * Java Program to find two elements in an array that sum to k.
 * 
 * @author WINDOWS 8
 */</i></font><font>
<b>public</b> <b>class</b> ArraySumUsingSet {

    <b>public</b> <b>static</b> <b>void</b> main(String args) {
       prettyPrint(getRandomArray(9), 11);
       prettyPrint(getRandomArray(10), 12);
    }

    </font><font><i>/**
     * Given an array of integers finds two elements in the array whose sum is equal to n.
     * @param numbers
     * @param n
     */</i></font><font>
    <b>public</b> <b>static</b> <b>void</b> pr<b>int</b>PairsUsingSet(<b>int</b> numbers, <b>int</b> n){
        <b>if</b>(numbers.length < 2){
            <b>return</b>;
        }        
        Set set = <b>new</b> HashSet(numbers.length);
        
        <b>for</b>(<b>int</b> value : numbers){
            <b>int</b> target = n - value;
            
            </font><font><i>// if target number is not in set then add</i></font><font>
            <b>if</b>(!set.contains(target)){
                set.add(value);
            }<b>else</b> {
                System.out.printf(</font><font>"(%d, %d) %n"</font><font>, value, target);
            }
        }
    }
    
    </font><font><i>/*
     * Utility method to find two elements in an array that sum to k.
     */</i></font><font>
    <b>public</b> <b>static</b> <b>void</b> prettyPr<b>int</b>(<b>int</b> random, <b>int</b> k){
        System.out.println(</font><font>"Random Integer array : "</font><font> + Arrays.toString(random));
        System.out.println(</font><font>"Sum : "</font><font> + k);
        System.out.println(</font><font>"pair of numbers from an array whose sum equals "</font><font> + k);
        printPairsUsingSet(random, k);
    }
    
    </font><font><i>/**
     * Utility method to return random array of Integers in a range of 0 to 15
     */</i></font><font>
    <b>public</b> <b>static</b> <b>int</b> getRandomArray(<b>int</b> length){
        <b>int</b> randoms = <b>new</b> <b>int</b>[length];
        <b>for</b>(<b>int</b> i=0; i<length; i++){
            randoms
</font>

= (<b>int</b>) (Math.random()*15);
        }
        <b>return</b> randoms;
    }

}

Output:
Random Integer array : [0, 14, 0, 4, 7, 8, 3, 5, 7]
Sum : 11
pair of numbers from an array whose sum equals 11
(7, 4) 
(3, 8) 
(7, 4) 
Random Integer array : [10, 9, 5, 9, 0, 10, 2, 10, 1, 9]
Sum : 12
pair of numbers from an array whose sum equals 12
(2, 10)

还有一件事，我们在这里使用HashSet，但由于Java中的HashSet内部使用HashMap，如果使用这些数据结构，它将没有任何区别。这个解决方案几乎没有约束，它需要额外的O阶空间（ n）在Hashtable或Set中存储数字，因此如果数组非常大，你需要额外的空间可能会有问题（记住我们在编写解决方案之前问过的问题）。对于大型阵列，您需要一个不需要额外空间的解决方案，也称为就地解决方案。如果面试官会问你如何找到一个数组中的两个值是否总和到一个给定值而没有任何额外的空间，那么第一个解决方案也不会起作用，因为它的复杂性太高而且对一个大数组进行排序太长了。复杂的解决方案，例如O（n），O（logN）或O（NLongN）应该可以工作。更有效的就地解决方案是对数组进行排序并使用两个指针从两个方向（即开始和结束）扫描数组。如果两个值的总和等于给定数，那么我们输出该对并推进它们。如果两个数之和小于k，那么我们增加左指针，否则如果总和大于k，我们递减右指针，直到两个指针在数组的某个部分相遇。由于排序，该解决方案的复杂性将是O（NlogN）。请记住使用像quicksort这样的就地排序算法来对数组进行排序，因为我们没有额外的空间。值得庆幸的是，Arrays.sort（）方法使用两个pivot快速排序算法来对基元数组进行排序。

<b>import</b> java.util.Arrays;
<b>import</b> java.util.HashSet;
<b>import</b> java.util.Set;

<font><i>/**
 * Java Program to find all pairs on integer array whose sum is equal to k
 * 
 * @author WINDOWS 7
 */</i></font><font>
<b>public</b> <b>class</b> PrintArrayPairs {

    <b>public</b> <b>static</b> <b>void</b> main(String args) {
       prettyPr<b>int</b>( <b>new</b> <b>int</b>{ 12, 14, 17, 15, 19, 20, -11}, 9);
       prettyPr<b>int</b>( <b>new</b> <b>int</b>{ 2, 4, 7, 5, 9, 10, -1}, 9);
    }

    </font><font><i>/**
     * Given a number finds two numbers from an array so that the sum is equal to that number k.
     * @param numbers
     * @param k
     */</i></font><font>
    <b>public</b> <b>static</b> <b>void</b> pr<b>int</b>PairsUsingTwoPo<b>int</b>ers(<b>int</b> numbers, <b>int</b> k){
        <b>if</b>(numbers.length < 2){
            <b>return</b>;
        }
        Arrays.sort(numbers);
        
        <b>int</b> left = 0; <b>int</b> right = numbers.length -1;
        <b>while</b>(left < right){
            <b>int</b> sum = numbers
</font>

[left]

+ numbers

[right]

;
            <b>if</b>(sum == k){
                System.out.printf(<font>"(%d, %d) %n"</font><font>, numbers
</font>

[left]

, numbers

[right]

);
                left = left + 1;
                right = right -1;
                
            }<b>else</b> <b>if</b>(sum < k){
                left = left +1;
                
            }<b>else</b> <b>if</b> (sum > k) {
                right = right -1;
            }
        }
       
    }
    
    <font><i>/*
     * Utility method to print two elements in an array that sum to k.
     */</i></font><font>
    <b>public</b> <b>static</b> <b>void</b> prettyPr<b>int</b>(<b>int</b> random, <b>int</b> k){
        System.out.println(</font><font>"input int array : "</font><font> + Arrays.toString(random));
        System.out.println(</font><font>"All pairs in an array of integers whose sum is equal to a given value "</font><font> + k);
        printPairsUsingTwoPointers(random, k);
    }
    
}

Output :
input <b>int</b> array : [12, 14, 17, 15, 19, 20, -11]
All pairs in an array of integers whose sum is equal to a given value 9
(-11, 20) 
input <b>int</b> array : [2, 4, 7, 5, 9, 10, -1]
All pairs in an array of integers whose sum is equal to a given value 9
(-1, 10) 
(2, 7) 
(4, 5) 
</font>

在这个基于数组的面试问题上，找出一个整数数组中的所有对，其和等于给定整数。我们已经看到了解决这个问题的三种方法，从最简单的蛮力解决方案到可接受的O（N），再加上额外的空间和O（nlogn）。如果有人想做更多的练习，我建议为这个问题编写JUnit测试用例，给定一组约束，即使数组包含重复的，并且在这些解决方案上发现错误，也只需要打印唯一的对。或者，您也可以尝试解决它的表亲问题，给定一个整数数组，检查是否有3个数字的总和为0或给定的数字。记住，旅行比到达目的地更有趣：）

练习：

1）为此问题编写JUnit测试，并检查每个解决方案是否通过这些测试。

2）在时间和空间复杂性方面提出更好的解决方案？

3）找出这些解的边界条件。[/right][/left][/right][/left]

原文 https://www.jdon.com/51570

正文到此结束