Есть массив a состоящий из n целых чисел. Есть ли в массиве два различных индекса i и j такие,
что ai + aj равна сумме всех остальных чисел массива?
1 ответ
Решение за O(n*log(n))
с помощью метода двух указателей:
Для начала найдем сумму массива и положим ее в переменную s
Отсортируем массив и ставим левый указатель на левый конец массива, то есть l = 0
и правый указатель на правый конец массива, r = n - 1
.
- Если
a[l] + a[r] < s / 2
, тоl += 1
. - Иначе, если
a[l] + a[r] > s / 2
, тоr -= 1
- Иначе, мы нашли пару индексов.
Решение с помощью хэш-таблиц за O(n)
в среднем и O(n^2)
в худшем:
Аналогично находим сумму s
.
Запихнем все элементы массива в хэш-таблицу и на каждый ключ будем хранить индекс элемента, а далее начинаем итерироваться исходному массиву. И если существует такое i
, что существует элемент hash[s / 2 - a[i]]
, то очевидно решение существует и его будет легко восстановить. Естественно надо будет учесть, как в хэш-таблице разобраться с тем, что мы не можем на каждый ключ хранить несколько индексов (вдруг вышло так, что есть хотя бы 2 одинаковых элемента). Однако проблем с этим не должно быть. Можно сделать проверку i == hash[s/2 - a[i]]
и ее будет вполне достаточно.
-
-
@StanislavVolodarskiy может, но как мне изначально показалось необходимости в этом нет, по причине не хотелось перебирать элементы списка, ибо сложность будет линейной. Однако нам и не нужно перебирать все элементы списка, 2 элемента посмотреть будет достаточно, чтобы убедиться, что есть хотя бы два разных индекса– Learpcs6 мар 2022 в 10:00
[1, 1, 2, 2]
- тут два максимума не сработают. Есть другое решение.