这个问题是在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方案？一个能进一步减少时间复杂度的解决方案。
使用集合（set）可以在O(N)的时间和空间复杂度内轻松解决这个问题。首先将数组中所有元素添加到集合中，然后遍历数组中的每个元素，并检查K-ar[i]是否存在于集合中。
以下是Java代码，具有O(N)复杂度：
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");
这里是一个Java实现，时间复杂度与用于对数组排序的算法相同。请注意，这比您的第二个想法更快，因为我们不需要每次检查数字时都在整个数组中搜索匹配的伴侣。
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（不失一般性）。假设a[0,n]包含p1和p2。如果不包含，则算法显然正确。
基本情形（i=0，j=n）：
a[0,-1]不包含p1，a[n,n+1]不包含p2。
假设：
a[0,i-1]不包含a[i]，a[j+1,n]不包含p2。
步骤情况（从i到i + 1或从j到j - 1）：
p1 = a[i]。那么，由于p1 + a[j] < p1 + p2，必须增加索引j。但是根据假设，我们知道a[j+1,n-1]不包含p2。矛盾。因此，p1 != a[i]。由于每次迭代a[0，i-1]和a[j+1，n]都不包含p1和p2，因此a[i，j]包含p1和p2。最终，a[i] = p1且a[j] = p2，算法返回true。
这是一个具有O(n)时间复杂度和O(n)空间复杂度的Java实现。思路是使用一个HashMap，其中包含每个数组元素相对于目标的补数。如果找到补数，则存在两个数组元素之和等于目标。
public boolean twoSum(int[] nums, int target) {
if(nums.length == 0 || nums == null) return false;
Map<Integer, Integer> complementMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int curr = nums[i];
if(complementMap.containsKey(target - curr)){
return true;
}
complementMap.put(curr, i);
}
return false;
}
如果您想查找成对计数，
pairs = [3,5,7,10]
k = 17
counter = 0
for i in pairs:
if k - i in pairs:
counter += 1
print(counter//2)
def pair_count(_list, k): return sum([k - j in _list for i in _list]) // 2。这个方法有效是因为 True == 1，而 sum() 函数会计算生成器中有多少个元素为真。显然，这又回到了原始问题——将返回语句替换为 return any(k - j in _list for i in _list)，这可能更加高效，因为 any 在第一次出现 True 时就返回 True，这意味着在某些情况下你不必遍历 list_ 的每个元素。 - selplaceiPython解决方案：
def FindPairs(arr, k):
for i in range(0, len(arr)):
if k - arr[i] in arr:
return True
return False
A = [1, 4, 45, 6, 10, 8]
n = 100
print(FindPairs(A, n))
或者
def findpair(list1, k):
for i in range(0, len(list1)):
for j in range(0, len(list1)):
if k == list1[i] + list1[j]:
return True
return False
nums = [10, 5, 6, 7, 3]
k = 100
print(findpair(nums, k))
以下是Python的实现：
arr=[3,5,7,10]
k=17
flag=False
hashset = set()
for i in range(0,len(arr)):
if k-arr[i] in hashset:
flag=True
hashset.add(arr[i])
print( flag )
Javascript解决方案：
function hasSumK(arr, k) {
hashMap = {};
for (let value of arr) {
if (hashMap[value]) { return true;} else { hashMap[k - value] = true };
}
return false;
}
该解决方案可以在数组的一次遍历中找到。初始化哈希集合并开始迭代数组。如果在集合中找到了数组中的当前元素，则返回 true，否则将此元素的补数（x-arr[i]）添加到集合中。如果数组的迭代结束而没有返回，则意味着没有这样的一对，使得它们的和等于 x，因此返回 false。
public boolean containsPairWithSum(int[] a, int x) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i< a.length; i++) {
if(set.contains(a[i]))
return true;
set.add(x - a[i]);
}
return false;
}
import collection.mutable.HashMap
def addUpToK(arr: Array[Int], k: Int): Option[Int] = {
val arrayHelper = new HashMap[Int,Int]()
def addUpToKHelper( i: Int): Option[Int] = {
if(i < arr.length){
if(arrayHelper contains k-arr(i) ){
Some(arr(i))
}else{
arrayHelper += (arr(i) -> (k-arr(i)) )
addUpToKHelper( i+1)
}
}else{
None
}
}
addUpToKHelper(0)
}
addUpToK(Array(10, 15, 3, 7), 17)
arrayHelper contains将会对值进行一次遍历。最坏情况下，这也是O(n^2)。 - D. McDermottC++解决方案：
int main(){
int n;
cin>>n;
int arr[n];
for(int i = 0; i < n; i++)
{
cin>>arr[i];
}
int k;
cin>>k;
int t = false;
for(int i = 0; i < n-1; i++)
{
int s = k-arr[i];
for(int j = i+1; j < n; j++)
{
if(s==arr[j])
t=true;
}
}
if (t){
cout<<"Thank you C++, very cool";
}
else{
cout<<"Damn it!";
}
return 0;
}
O(n)，空间复杂度也为O(n)的算法。对于每个元素，检查它是否存在于哈希表中。如果不存在，则将k-arr[i]存储起来，并继续下一个元素。 - thebenman