Задача C. Пара чисел
Есть массив 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]] и ее будет вполне достаточно.