给定一个数字列表和一个数字k，返回列表中的任意两个数字加起来是否等于k

Question

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

>

找出长度的所有子序列。这样做时，计算两个元素的和，并检查它是否等于k。如果是，请打印“是”，否则继续搜索。这是一种暴力手段。

按非降序排列数组。然后从数组的右端开始遍历数组。假设我们有一个排序数组，{3,5,7,10}，我们希望总和是17。我们将从元素10开始，索引=3，让我们用“j”来表示索引。然后包含当前元素并计算所需的_sum=sum-current_元素。之后，我们可以在数组[0-（j-1）]中执行二元或三元搜索，以确定是否存在一个值等于所需_和的元素。如果我们找到这样一个元素，我们可以分解，因为我们找到了一个长度为2的子序列，其和就是给定的和。如果我们找不到任何这样的元素，则减小j的索引，并重复上述步骤，得到长度=长度-1的子阵列，即在这种情况下排除索引3处的元素。

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

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

Answer 1

这是一个具有O（n）时间复杂度和O（n）空间的java实现。其想法是创建一个HashMap，其中包含每个数组元素w.r.t目标的补码。如果找到了补码，我们有两个数组元素，它们的和就是目标。

 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;
}

Answer 2

下面是一个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]为长度为n1和p=（p1，p2）的数组，其中p1，p2是整数，p1

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

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

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

1. 假设p1=a[i]。然后，由于p1 a[j]

因为每次迭代，a[0，i-1]和a[j1，n]，都不包含p1，p2，a[i，j]确实包含p1和p2。最后，a[i]=p1和a[j]=p2算法返回true。

Answer 3

借助O（N）时间复杂度中的set可以很容易地解决这个问题。首先将数组的所有元素添加到set中，然后遍历数组的每个元素，检查K-ar[i]是否存在于set中。

以下是复杂度为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");