Найти 2 числа в несортированном массиве, равном заданной сумме
Нам нужно найти пару чисел в массиве, сумма которого равна заданному значению.
A = {6,4,5,7,9,1,2}
Сумма = 10 Тогда пары - {6,4}, {9,1}
У меня есть два решения для этого.
решение O (nlogn) - сортировка + контрольная сумма с 2 итераторами (начало и конец).решение O (n) - хэширование массива. Затем проверка, еслиsum-hash[i]
существует в хеш-таблице или нет.Но проблема в том, что хотя второе решение - это O (n) время, но также используется пространство O (n).
Итак, мне было интересно, можем ли мы сделать это вНа) время иO (1) пространство. И это НЕ домашнее задание!