Является ли использование ArrayList.contains () внутри цикла for более эффективным, чем использование вложенных циклов для сравнения?

Question

Я давал несколько практических вопросов по собеседованию, и этот вопрос был довольно легким, но мне интересно, действительно ли более эффективное из моих двух решений таково.

Теперь я вижу, что кто-то еще здесь ранее задавал этот вопрос, но у моего вопроса есть фрагменты кода, и я упал, что он может дать дополнительную информацию для всех, кто ищет решение.

Вопрос в том, что: при наличии массива целых чисел и некоторого числа k создайте функцию, которая возвращает значение true, если любые два числа в массиве добавят к k .

Вот мое "медленное" решение:

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 (), который в любом случае использует для циклов, поэтому он может быть столь же неэффективным и просто запутанным. Есть ли какая-нибудь магия вуду, которая делает второе решение более эффективным? Если нет, то есть ли способ сделать это более эффективным или это лучшее, что вы можете сделать? Интересно, будет ли какая-то разница в хеш-таблице?

Answer 1

Эффективность не отличается в обоих случаях, потому что 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;
}

Answer 2

Вот решение 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²) и не использует никакого дополнительного пространства.