arrays - 给定一个数字列表和一个数字 k，返回列表中的任意两个数字是否相加为 k

Question

这个问题是在谷歌编程面试中被问到的。我想到了两种相同的方法:

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

2. 按非递减顺序对数组进行排序。然后从右端开始遍历数组。假设我们有排序数组 {3,5,7,10}，我们希望总和为 17。我们将从元素 10 开始，索引 = 3，让我们用“j”表示索引。然后包含当前元素并计算 required_sum= sum - current_element。之后，我们可以在数组[0-(j-1)]中进行二元或三元查找，查找是否存在值等于required_sum的元素。如果我们找到这样一个元素，我们可以打破，因为我们已经找到了一个长度为 2 的子序列，其总和是给定的总和。如果我们没有找到任何这样的元素，则减少 j 的索引并重复上述步骤以获得 length = length-1 的结果子数组，即在这种情况下排除索引 3 处的元素。

这里我们考虑了数组可以有正整数也可以有负整数。

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

Answer 1

这道题用时间空间复杂度为O(N)的集合很容易解决。首先将数组中的所有元素加入集合中，然后遍历数组中的每个元素，判断K-ar[i]是否为存在与否。

这是复杂度为 O(N) 的 java 代码:

boolean flag=false;
HashSet<Long> hashSet = new HashSet<>();
for(int i=0;i<n;i++){
    if(hashSet.contains(k-ar[i]))flag=true;
    hashSet.add(ar[i]);
}
if(flag)out.println("YES PRESENT");
else out.println("NOT PRESENT");