这个问题是在Google的编程面试中提出的。我想到了两种方法：
找到所有长度为n的子序列，计算两个元素的和并检查它是否等于k。如果是，则打印Yes，否则继续搜索。这是一种暴力的方法。
将数组按非递减顺序排序。然后从其右侧开始遍历数组。假设我们有一个已排序的数组{3,5,7,10}，我们想让总和为17。我们将从元素10开始，索引=3，用“j”表示索引。然后包括当前元素并计算required_sum = sum-current_element。之后，我们可以在array [0-(j-1)] 中执行二元或三元搜索，以查找其值等于required_sum的元素。如果我们找到这样的元素，那么我们可以停止搜索，因为我们已经找到了一个长度为2且总和为给定总和的子序列。如果我们没有找到这样的元素，则将j的索引减小，并针对长度为length-1的结果子数组（在这种情况下排除索引3处的元素）重复上述步骤。
这里我们考虑到数组可能包含负数和正数整数。
您能推荐比这更好的解决方案吗？也许是DP方案？一个能进一步减少时间复杂度的解决方案。
C# 解决方案：
bool flag = false;
var list = new List<int> { 10, 15, 3, 4 };
Console.WriteLine("Enter K");
int k = int.Parse(Console.ReadLine());
foreach (var item in list)
{
flag = list.Contains(k - item);
if (flag)
{
Console.WriteLine("Result: " + flag);
return;
}
}
Console.WriteLine(flag);
function ProblemOne_Solve()
{
const k = 17;
const values = [10, 15, 3, 8, 2];
for (i=0; i<values.length; i++) {
if (values.find((sum) => { return k-values[i] === sum} )) return true;
}
return false;
}
我的C#实现：
bool isPairPresent(int[] numbers,int value)
{
for (int i = 0; i < numbers.Length; i++)
{
for (int j = 0; j < numbers.Length; j++)
{
if (value - numbers[i] == numbers[j])
return true;
}
}
return false;
}
这里是一个Scala的解决方案，它超越了布尔结果并返回它存在的一对：
def thereIs(list2check: List[Int], k: Int): List[Int] = list2check match {
case Nil => Nil
case x :: tail => tail.flatMap{
case element if (element+ x)==k =>List(element,x)
case element if (element+ x)!=k => Nil
} ++ thereIs(tail,k)
}
Python
def add(num, k):
for i in range(len(num)):
for j in range(len(num)):
if num[i] + num[j] == k:
return True
return False
大多数发布的解决方案没有考虑到k是列表中任何数字的两倍，因此它们的解决方案会生成错误的结果。下面的代码也考虑了这种情况。由于涉及集合的操作是O(1)，我们的最终解决方案是单次遍历O(N)的解决方案。
from typing import Optional, List
def add_upto_k(k: int, array: Optional[List] = None) -> bool:
assert array, "Non array input"
assert len(array) != 0, "Array is empty"
diff_set = set()
for iterator in array:
diff = k - iterator
if iterator in diff_set:
return True
diff_set.add(diff)
return False
if __name__ == "__main__":
print(add_upto_k(k=17, array=[10, 15, 3, 7])) # True
print(add_upto_k(k=15, array=[10, 15, 3, 7])) # False
print(add_upto_k(k=20, array=[10, 15, 3, 10])) # True
print(add_upto_k(k=20, array=[10, 15, 3, 7])) # False
每日编程问题发布了一个与您的问题相关的版本...
给定一个数字列表和一个数字 k，返回列表中是否有任何两个数字相加等于 k。
例如，给定 [10, 15, 3, 7] 和 k 等于 17，返回 true，因为 10 + 7 = 17。
额外题目：你能否一次遍历解决这个问题？
下面是基于您的第二个建议的 Ruby 实现。我不确定是否可以进行优化。
假设：“数字列表”实际上是一组数字。
def one_pass_solution
k = 17
arr = [10, 15, 3, 7]
l = 0
r = arr.length-1
arr.sort!
while l < r do
if arr[l] + arr[r] < k
l += 1
elsif arr[l] + arr[r] > k
r -= 1
else
return true
end
end
return false
end
具有O(N)的复杂度
private static boolean check_add_up(int[] numbers, int total) {
Set<Integer> remainders = new HashSet<>();
int remainder;
for (int number : numbers ) {
if (remainders.contains(number)) {
return true;
}
remainder = total - number;
if(!remainders.contains(remainder)){
remainders.add(remainder);
}
}
return false;
}
Javascript 解决方案
function matchSum(arr, k){
for( var i=0; i < arr.length; i++ ){
for(var j= i+1; j < arr.length; j++){
if (arr[i] + arr[j] === k){
return true;
}
}
}
return false;
}
C++解决方案。
注意：需要C++20（因为使用了'contains'）
复杂度O(N)（因为在哈希映射中插入和搜索的复杂度为O(1)）
Wandbox的工作链接：https://wandbox.org/permlink/KPlzNIlKnTrV5z4X
#include <iostream>
#include <vector>
#include <unordered_map>
#include <optional>
using opt = std::optional<std::pair<int, int> >;
template <class T, class U>
std::ostream& operator<<(std::ostream& out, const std::pair<T, U>& p)
{
out << "(" << p.first << ", " << p.second << ")";
return out;
}
opt check(std::vector<int> nums, int k)
{
std::unordered_map<int, int> ht;
for (const auto& n : nums) {
if (ht.contains(n)) {
return opt({ ht[n], n });
}
ht[k - n] = n;
}
return std::nullopt;
}
int main()
{
auto res = check({ 10, 15, 3, 7 }, 17);
if (res)
std::cout << *res << std::endl;
else
std::cout << "Not found" << std::endl;
}
O(n)，空间复杂度也为O(n)的算法。对于每个元素，检查它是否存在于哈希表中。如果不存在，则将k-arr[i]存储起来，并继续下一个元素。 - thebenman