проверка, если 2 числа массива складываются в I

Question

Я видел вопрос интервью следующим образом: Дайте несортированный массив целых чисел A и и целое число I, выясните, если любые два члена A складываются в I.

какие-нибудь подсказки?

сложность времени должна быть меньше

Answer 1

Эту проблему можно решить с помощью алгоритма UNION-FIND, который может в постоянное время проверять, входит ли элемент в набор.

Итак, алгоритм будет выглядеть так:* FIND и UNION постоянны, O (1).

Answer 2

Это может быть возможно следующим образом: Перед помещением элементов в хэш-карту вы можете проверить, превышает ли элемент требуемую сумму. Если это так, вы можете просто пропустить этот элемент, иначе вы можете продолжить помещать его в hashmap. Это небольшое улучшение вашего алгоритма, хотя общее время остается прежним.

Answer 3

Реализация PERL для определения, содержит ли отсортированный массив два целых числа, которые суммируются до числа

my @a = (11,3,2,9,12,15);
my @b = sort {$a <=> $b} @a;

my %hash;
my $sum = 14;
my $index = 0;
foreach my $ele (@b) {
    my $sum_minus_ele = $sum - $ele;
    print "Trace: $ele :: $index :: $sum_minus_ele\n";
    if(exists($hash{$sum_minus_ele}) && $hash{$sum_minus_ele} != $index ) {
        print "\tElement: ".$ele." :: Sum-ele: ".$sum_minus_ele."\n";
    }
    $hash{$ele} = $index;
    $index++;
}

Answer 4

for each ele in the array
  if (sum - ele) is hashed and hashed value is not equal to index of ele
    print ele, sum-ele
  end-if
  Hash ele as key and index as value
end-for

Answer 5

для nlogn: отсортировать массив и для каждого элемента [0<=j<len A] вычесть i-A[j] и выполнить двоичный поиск для этого элемента в отсортированном массиве.

hashmap (frequency of no, number) должно работать в O(n).