Определите, существуют ли там два элемента в Наборе S, чья сумма точно x - правильное решение?

Ваш анализ правильный, и да, вы должны отсортировать массив или двоичный поиск не работает.

Невозможно, так как «X с Y» является анонимным определением в примере. Конечно, это не относится к «классу X, расширяющему Z с Y».

Я думаю, что я заметил небольшую ошибку в вашей реализации, но тестирование должно быстро раскрыть эту ошибку.

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

int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
    while (a[i] + a[j] > val) {
        j--;
    }
    if (a[i] + a[j] == val) {
        // heureka!
    }
}

Этот шаг является O (n). (Доказать, что это оставлено как упражнение для вас.) Конечно, весь алгоритм по-прежнему принимает O (n log n) для сортировки слиянием.

Существует еще одно очень быстрое решение: Представьте, что вы должны решить эту задачу на Java для около 1 миллиарда целых чисел. Известно, что в Java целые числа переходят от -2 * * 31 + 1 к + 2 * * 31 .

Создайте массив с 2 * * 32 миллиардными битами (500 МБ, тривиально для современного оборудования).

Выполните итерацию над набором: если имеется целое число, установите соответствующий бит в 1.

O (n).

Повторите итерацию над набором: для каждого значения проверьте, установлен ли бит на «current val - x».

Если он у вас есть, вы возвращаете значение true.

Необходимо 500 МБ памяти.

Но это будет работать вокруг любого другого O (n log n) решения, если у вас есть, скажем, чтобы решить эту проблему с 1 миллиардом целых чисел.

O (n).

Вот раствор O (N) с использованием хеш-набора:

  public static boolean test(int[] a, int val) {
      Set<Integer> set = new HashSet<Integer>();

      // Look for val/2 in the array
      int c = 0;
      for(int n : a) {
        if(n*2 == val)
          ++c
      }
      if(c >= 2)
         return true; // Yes! - Found more than one

      // Now look pairs not including val/2
      set.addAll(Arrays.asList(a));
      for (int n : a) {
         if(n*2 == val)
            continue;
         if(set.contains(val - n))
            return true;
      }

      return false;
   }

Невозможно, так как «X с Y» является анонимным определением в примере. Конечно, это не относится к «классу X, расширяющему Z с Y».

Я думаю, что я заметил небольшую ошибку в вашей реализации, но тестирование должно быстро раскрыть эту ошибку.

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

int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
    while (a[i] + a[j] > val) {
        j--;
    }
    if (a[i] + a[j] == val) {
        // heureka!
    }
}

Этот шаг является O (n). (Доказать, что это оставлено как упражнение для вас.) Конечно, весь алгоритм по-прежнему принимает O (n log n) для сортировки слиянием.

1. Это правильно; ваш алгоритм будет запущен через O (n lg n) раз.

2. Есть лучшее решение: ваша логика вычисления diff неверна. Независимо от того, является ли a [i] больше или меньше val , все равно нужно, чтобы diff был val - a [i] .

Если нам разрешено принимать, что вход можно отсортировать в O (N) с помощью Radix, я бы немного улучшился на растворе Криса:

• RADIX сортирует вход.
• Для первого элемента результата, линейный поиск вперед, пока мы не найдем ни своего квадрата (в этом случае останавливается с true), либо конец (в этом случае останавливается с false) или остальное значение больше, чем квадрат ( В этом случае продолжайте поиск квадрата второго и последующих элементов отсортированного массива).

Каждый из двух «указателей» движется строго вперед, поэтому общая сложность является O (N), предполагая, что сортировка RADIX является O (N) и что квадрат и сравнение o (1). Предположительно, кто наставил вопрос, предполагаемый эти предположения.

В ответ на комментарий вопросителя по другому ответу: если целые числа на входе не ограничены, то я не думаю, что это может быть сделано. Просто расчета квадрата целого числа требуется больше линейного времени (по крайней мере: ни один линейный алгоритм для умножения не известен), поэтому рассмотрим ввод размера N битов, состоящий из двух целых чисел размером N / 3 . и 2 * N / 3 бит. Тестирование того, является ли один квадрат другой, не может быть сделан в O (n). Я думаю. Я могу ошибаться.

Простое решение - это, после сортировки, перемещайте указатели с обоих концов массива, ищете пары, которые сумма на X. Если сумма слишком высока, уменьшайте правильный указатель. Если слишком низко, увеличивайте левый. Если указатели креста, ответ нет.

Я действительно думаю, что заметил небольшую ошибку в вашей реализации, но тестирование должно быстро ее обнаружить.

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

int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
    while (a[i] + a[j] > val) {
        j--;
    }
    if (a[i] + a[j] == val) {
        // heureka!
    }
}

Этот шаг - O(n). (Доказывая, что это оставлено как упражнение для вас.) Конечно, весь алгоритм все еще принимает O(n log n) для сортировки слияния.