java - 在 for 循环中使用 ArrayList.contains() 实际上比使用嵌套循环进行比较更有效吗？

Question

我一直在练习一些技术面试问题，这个问题非常简单，但我想知道我的两个解决方案中效率更高的是否真的如此。

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

问题是:给定一个整数数组和一些数字 k，创建一个函数，如果数组中的任意两个数字相加到 k 则返回 true。k p>

这是我的“慢速”解决方案:

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 循环，因此它可能同样低效且被混淆了。是否有任何巫术可以使第二种解决方案更有效？如果没有，是否真的有办法提高效率，或者这是您能做的最好的事情？我想知道哈希表是否会有所作为。

Answer 1

两种情况下效率没有区别，因为list.contains()的时间复杂度是O(n)，所以两者的时间复杂度都是< em>O(n²).

更好的解决方案是使用 HashSet.contains()其时间复杂度为 O(1)。

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. (docs)

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