给定一个数字列表和一个数字k,返回列表中的任何两个数字是否加起来为k

Question

Google编程面试中提到了这个问题.我想到了两种相同的方法:

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

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

在这里,我们认为数组可能有负整数和正整数.

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

Answer 1

借助于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");

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

Answer 3

这是具有 O(n) 时间复杂度和 O(n) 空间的 Java 实现。这个想法是有一个 HashMap 它将包含每个数组元素wrt目标的补充。如果找到补码，我们有 2 个数组元素，它们与目标相加。

 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 4

如果要查找对数，

pairs = [3,5,7,10]
k = 17
counter = 0

for i in pairs:
    if k - i in pairs:
        counter += 1

print(counter//2)