我一直在做一些练习技术面试问题，这个问题很容易，但我想知道我的两个解决方案中是否真的更有效。
我现在看到这里的其他人以前问过这个问题，但我的问题有代码片段，我跌倒了，它可能会为正在寻找解决方案的其他任何人提供进一步的见解。
问题是：给定一个整数数组和一些数字k，创建一个函数，如果数组中的任何两个数字加到k时返回 true。
这是我的"慢"解决方案：
private static boolean canAddToKSlow(int[] nums, int k) {
/*
Uses double for loops to compare each value in the array to
another value (not including the current one). If they add
up to k, return true. Otherwise, at the end of iteration,
return false.
*/
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < nums.length; j++) {
if (j != i) {
if (nums[i] + nums[j] == k) {
return true;
}
}
}
}
return false;
}
和我的"快速"解决方案：
private static boolean canAddToKFast(int[] nums, int k) {
/*
Uses a single optimized for loop to iterate through the list,
and adds the "complement" of the current int to the arraylist.
By complement, I mean whatever number you would have to add to
n to get k. Then, it checks to see if that n is in the arraylist, and if so, then there must be two numbers that
add to k. More efficient.
*/
ArrayList<Integer> comps = new ArrayList<>();
for(int n: nums) {
comps.add(k - n);
if(comps.contains(n))
return true;
}
return false;
}
我在这里遇到的问题是 ArrayList.contains() 调用 indexOf()，它无论如何都使用 for 循环，所以它可能同样效率低下并且只是混淆。有没有巫毒魔法使第二种解决方案更有效率？如果没有，是否有办法使其更有效率，或者这是你能做的最好的事情吗？我想知道哈希表是否会有任何不同。
两种情况下的效率没有区别，因为list.contains()的时间复杂度为 O(n)，因此两者的时间复杂度均为O(n²)。
更好的解决方案是使用时间复杂度为 O(1)的HashSet.contains()。
此类为基本操作(添加、删除、包含和大小)提供恒定的时间性能，假设哈希函数在存储桶中正确分散元素。(文档)
所以它的时间复杂度是O(n)：
private static boolean canAddToKFast2(int[] nums, int k) {
Set<Integer> comps = new HashSet<>();
for (int n : nums) {
if (comps.contains(n))
return true;
comps.add(k - n);
}
return false;
}
下面是一个使用哈希表的 O(n) 解决方案，但它确实使用了额外的空间：
private static boolean canAddToKFast2(int[] nums, int k) {
Map<Integer,Integer> table = new HashMap<Integer, Integer>();
for(int val: nums) {
if(table.containsKey(k - val)) { // O(1) lookup to see if the difference exists
return true;
}
table.put(val, val); //If it doesn't exist, add the value to the table
}
return false; // We searched all values and didn't find a pair
}
这是O(n)时间，我们可以看到，因为我们只接触每个元素一次。如果表中不存在目标减号元素，则将其插入表中。如果我们遍历所有项目但找不到匹配项，则返回 false。
空间效率如何？
关于你的采访，我会问是否允许额外的空间(哈希表将使用O(n)空间)。如果不允许额外的空间，那么最有效的答案是问题中的代码(以 O(n²) 时间运行并且不使用任何额外的空间。