Алгоритм на основе Java, чтобы найти, есть ли в массиве 2 числа, сумма которых равна х

Question

Недавно я наткнулся на интересное утверждение алгоритма Java

Given an array int[] arr{} and a number x, find if there are any 2 numbers in the array whose sum is equal to x.

Подсказка: решите это тремя способами со следующими сложностями O(n^2), O(n log n) и O (n)

Подход O (n ^ 2) - это простая логика грубой силы. O (n log n) возможно включает в себя сортировку слиянием и использование бинарного поиска - хотя я могу точно выяснить, как вписаться в бинарный поиск здесь. Я совершенно не разбираюсь в алгоритме O (n).

Простая логика грубой силы:

for(i = 0; i < arr.length; i++){
    for(j=0; j<arr.length; j++){
       if(arr[i] + arr[j] == x){
         return x;
       }
    }
}

Есть указатели?

Answer 1

Вот решение на основе HashSet с n временной и пространственной сложностью.

 private static boolean twoNumbersInArraySumIsEqualToX(int[] input, int x) {
    //create HashSet and store each element as key from array
    Set<Integer> set =  new HashSet<Integer>();
    for (int elem_ : input) set.add(elem_);

    //Iterate through the array and find if (x - elem) exists in set
    for (int elem_ : input) {
      if(set.contains(x - elem_)) return true;
    }
    return false;
  }

Answer 2

Если мы предположим, что массив уже отсортирован, вы можете сделать следующее:

int i =0;
int j = arr.length-1;
while (i<j){
    if (arr[i]+arr[j]>x){
        j--;
        continue;
    }
    else if (arr[i]+arr[j]<x){
        i++;
        continue;
    }
    else { // arr[i]+arr[j]==x
        return true;
    }
}
return false;

Answer 3

Я думаю, что предполагаемое решение O(n) - это HashMap. Добавление и тестирование n значений - это O(n) или close.

PS: Несмотря на то, что за меня проголосовали, я поддерживаю свой ответ.

Хорошо, возможно я должен был объяснить алгоритм: для каждого a[i], проверьте, есть ли (xa[i]) в HashMap. Если да, то все готово. Если нет, добавьте [i] в ​​HashMap и продолжайте.