给定一个数字列表和一个数字k，返回列表中是否有两个数字加起来等于k [英] Given a list of numbers and a number k, return whether any two numbers from the list add up to k

问题描述

这个问题是在Google编程采访中提出的。我想到了两种相同的方法：

This question was asked in the Google programming interview. I thought of two approaches for the same:

1. 查找长度的所有子序列。这样做时，计算两个元素的和，然后检查它是否等于k。如果是，则打印是，否则继续搜索。这是一种蛮力的方法。

1. Find all the subsequences of length. While doing so compute the sum and of the two elements and check if it is equal to k. If ye, print Yes, else keep searching. This is a brute Force approach.

以非降序排列数组。然后从其右端开始遍历数组。假设我们有一个排序后的数组{3,5,7,10}，我们希望总和为17。我们将从元素10开始，index = 3，用'j'表示索引。然后包括当前元素并计算required_sum = sum-current_element。之后，我们可以在array [0-（j-1）]中执行二进制或三进制搜索，以查找是否存在一个值等于required_sum的元素。如果找到这样一个元素，我们就会发现长度为2的子序列，其总和就是给定的总和，因此我们可能会中断。如果找不到任何这样的元素，则减小j的索引，并重复上述步骤以生成长度= length-1的子数组，即在这种情况下，排除索引3的元素。

Sort the array in non-decreasing order. Then start traversing the array from its right end. Say we have the sorted array, {3,5,7,10} and we want the sum to be 17. We will start from element 10, index=3, let's denote the index with 'j'. Then include the current element and compute required_sum= sum - current_element. After that, we can perform a binary or ternary search in array[0- (j-1)] to find if there is an element whose value is equal to the required_sum. If we find such an element, we can break as we have found a subsequence of length 2 whose sum is the given sum. If we don't find any such element, then decrease the index of j and repeat the above-mentioned steps for resulting subarray of length= length-1 i.e. by excluding the element at index 3 in this case.

在这里，我们认为数组可以同时具有负整数和正整数。

Here we have considered that array could have negative as well as positive integers.

您能提出比这更好的解决方案吗？ DP解决方案？可以进一步降低其时间复杂度的解决方案。

Can you suggest a better solution than this? A DP solution maybe? A solution that can further reduce it's time complexity.

推荐答案

这里是Java实现，其时间复杂度与以前的算法相同对数组进行排序。请注意，这比您的第二个想法要快，因为我们不需要在每次检查数字时都在整个数组中寻找匹配的伙伴。

Here is a Java implementation with the same time complexity as the algorithm used to sort the array. Note that this is faster than your second idea because we do not need to search the entire array for a matching partner each time we examine a number.

public static boolean containsPairWithSum(int[] a, int x) {
    Arrays.sort(a);
    for (int i = 0, j = a.length - 1; i < j;) {
        int sum = a[i] + a[j];
        if (sum < x)
            i++;
        else if (sum > x)
            j--;
        else
            return true;
    }
    return false;
}

归纳证明：
让 a [0，n] 是长度为n + 1的数组，而 p =（p1，p2）其中p1 ，p2是整数，并且 p1< = p2 （wlog）。假设 a [0，n] 包含p1和p2。在这种情况下，算法显然是正确的。

Proof by induction: Let a[0,n] be an array of length n+1 and p = (p1, p2) where p1, p2 are integers and p1 <= p2 (w.l.o.g.). Assume a[0,n] contains p1 and p2. In the case that it does not, the algorithm is obviously correct.

基本情况（i = 0，j = n）：
a [0，-1] 不包含p1， a [n，n + 1] 不包含p1

Base case (i = 0, j = n): a[0,-1] does not contain p1 and a[n,n+1] does not contain p2.

假设：
a [0，i-1] 不包含 a [i] ，而 a [j + 1，n] 不包含p2。

Hypothesis: a[0,i-1] does not contain a[i] and a[j+1,n] does not contain p2.

分步情况（i至i + 1或j至j-1）：

1. 假设 p1 = a [i] 。然后，由于 p1 + a [j]< p1 + p2 ，索引j必须增加。但是从假设中我们知道 a [j + 1，n-1] 不包含p2。矛盾。因此， p1！= a [i] 。


2. j类似于j-1。

1. Assume p1 = a[i]. Then, since p1 + a[j] < p1 + p2, index j must be increased. But from the hypothesis we know that a[j+1,n-1] does not contain p2. Contradiction. It follows that p1 != a[i].
2. j to j - 1 analogously.

由于每次迭代， a [0，i-1] 和 a [j + 1，n] ，不包含 p1 和 p2 ， a [i，j] 确实包含 p1 和 p2 。最终， a [i] = p1 和 a [j] = p2 ，算法返回true。

Because each iteration, a[0,i-1] and a[j+1,n], does not contain p1, and p2, a[i,j] does contain p1 and p2. Eventually, a[i] = p1 and a[j] = p2 and the algorithm returns true.

这篇关于给定一个数字列表和一个数字k，返回列表中是否有两个数字加起来等于k的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！