正在使用ArrayList。for循环中的contains（）实际上比使用嵌套循环进行比较更有效？

Question

我一直在做一些实践技术面试问题，这个问题很容易，但是我想知道我的两个解决方案中更有效的是否真的如此。

我现在看到这里的其他人以前问过这个问题，但我的问题有代码片段，我觉得它可能会为其他正在寻找解决方案的人提供进一步的见解。

问题是：给定一个整数数组和一些数字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（），indexOf（）无论如何都会用于循环，因此它可能同样低效，而且只是混淆了。有没有巫毒魔法能让第二种解决方案更有效？如果没有，实际上有没有一种方法可以提高效率，或者这是你能做到的最好的方法？我想知道散列表是否会有什么不同。

Answer 1

下面是一个使用哈希表的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²）时间内运行，不使用任何额外的空间。

Answer 2

在这两种情况下，效率没有差别，因为list。contains（）的时间复杂度为O（n），因此两者的时间复杂度均为O（n²）。

更好的解决方案是使用HashSet。contains（）的时间复杂度为O（1）。

这个类为基本操作（添加、删除、包含和大小）提供了恒定的时间性能，前提是哈希函数将元素正确地分散在存储桶中。（文件）

所以这个的时间复杂度是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;
}