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

Ответ 1

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

public static boolean test(int[] a, int val) 
{
    Arrays.sort(a);

    int i = 0;            // index of first element.
    int j = a.length - 1; // index of last element. 

    while(i<j)
    {
        // check if the sum of elements at index i and j equals val, if yes we are done.
        if(a[i]+a[j] == val)
            return true;
        // else if sum if more than val, decrease the sum.
        else if(a[i]+a[j] > val)
            j--;
        // else if sum is less than val, increase the sum.
        else
            i++;
    }
    // failed to find any such pair..return false. 
    return false;
}

Ответ 2

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

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

Итерации по вашему набору: если у вас есть целое число, установите соответствующий бит в 1.

O (n) до сих пор.

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

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

Конечно, для этого требуется 500 МБ памяти.

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

О (п).

Ответ 3

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

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

Ответ 4

Здесь решение 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;
   }

Ответ 5

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

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

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) для сортировки слияния.

Ответ 6

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

Ответ 7

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

Ответ 8

Вот альтернативное решение, добавив еще несколько условий в mergesort.

public static void divide(int array[], int start, int end, int sum) {

    if (array.length < 2 || (start >= end)) {
        return;
    }
    int mid = (start + end) >> 1; //[p+r/2]
    //divide
    if (start < end) {
        divide(array, start, mid, sum);
        divide(array, mid + 1, end, sum);
        checkSum(array, start, mid, end, sum);
    }
}

private static void checkSum(int[] array, int str, int mid, int end, int sum) {

    int lsize = mid - str + 1;
    int rsize = end - mid;
    int[] l = new int[lsize]; //init
    int[] r = new int[rsize]; //init

    //copy L
    for (int i = str; i <= mid; ++i) {
        l[i-str] = array[i];
    }
    //copy R
    for (int j = mid + 1; j <= end; ++j) {
        r[j - mid - 1] = array[j];
    }
    //SORT MERGE
    int i = 0, j = 0, k=str;
    while ((i < l.length) && (j < r.length) && (k <= end)) {
    //sum-x-in-Set modification
    if(sum == l[i] + r[j]){
        System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + r[j]);            
    }
     if (l[i] < r[j]) {
            array[k++] = l[i++];
        } else {
            array[k++] = r[j++];
        }
    }
    //left over
    while (i < l.length && k <= end) {
        array[k++] = l[i++];
          //sum-x-in-Set modification
        for(int x=i+1; x < l.length; ++x){
            if(sum == l[i] + l[x]){
                System.out.println("THE SUM CAN BE OBTAINED with the values" + l[i] + " " + l[x]);
            }
        }
    }
    while (j < r.length && k <= end) {
        array[k++] = r[j++];
          //sum-x-in-Set modification
        for(int x=j+1; x < r.length; ++x){
            if(sum == r[j] + r[x]){
                System.out.println("THE SUM CAN BE OBTAINED with the values" + r[j] + " " + r[x]);
            }
        }
    }
}

Но сложность этого алгоритма все еще не равна THETA (nlogn)