Пусть дан массив и некое число x. Надо определить, существуют ли в нем три числа, сумма которых равна х. Если было бы два числа - можно было бы отсортировать и бинпоиском для каждого числа a проверять наличие x - a. А тут как?
-
Элементы положительные? 4 прогона по циклу думаю достаточно– Senior Pomidor17 июн 2017 в 19:30
-
А точно так же... отсортировать - и понеслася. Цикл в цикле, а внутри твой бин-поиск.– Akina17 июн 2017 в 19:38
-
Связанный вопрос Finding three elements in an array whose sum is closest to a given number– jfs17 июн 2017 в 21:27
1 ответ
Update: реализация алгоритма, представленного ниже, не работает. К примеру: find_triplet_sum([0, 1, 2, 4, 5], 8)
не находит тройку индексов: 1, 2, 4.
Чтобы найти индексы i,j,k
в массиве a
, такие что a[i] + a[j] + a[k] == x
, существует O(n * log n)
алгоритм (из ответа @olykos):
- Отсортировать массив
- Выбрать индексы
lo
,hi
, соответствующие наибольшим и наименьшим значениям в массиве (первый и последний элементы в отсортированном массиве) Затем, до тех пор пока можно выбрать третий элемент между lo, hi индексами:
с помощью двоичного поиска пытаемся найти
i
индекс, такой что:a[lo] + a[i] + a[hi] == x
если нашли, то алгоритм завершён
- если сумма меньше, то увеличиваем
lo
(увеличиваем наименьший доступный элемент) - если сумма больше, то уменьшаем
hi
(уменьшаем наибольший доступный элемент)
- Если не нашли, то алгоритм завершился неуспешно.
Реализация на Питоне:
from bisect import bisect_left
def find_triplet_sum(a, x):
a.sort()
lo, hi = 0, len(a) - 1
while lo + 1 < hi:
i = bisect_left(a, x - a[lo] - a[hi], lo + 1, hi) # binary search
assert lo < i
triplet_sum = a[lo] + a[i] + a[hi]
if i == hi or triplet_sum < x: # sum is too small
lo += 1
elif triplet_sum > x: # sum is too big
hi -= 1
else: # found
assert lo < i < hi and triplet_sum == x
return lo, i, hi
raise ValueError("Can't find i,j,k such that: a[i] + a[j] + a[k] == x.")
где bisect_left()
реализует двоичный поиск. Пример:
>>> find_triplet_sum([0, 1, 2, 3, 4], 3)
(0, 1, 2)
-
Не совсем понятно: если сумма меньше. Если двоичный поиск завершился безрезультатно, то некоторые суммы могут быть меньше, а некоторые больше.– VladD18 июн 2017 в 15:09
-
@VladD: на следующей строчке в ответе: если сумма больше (больше, меньше, равно -- других вариантов нет)– jfs18 июн 2017 в 15:12
-
Всё равно непонятно. Двоичный поиск ничего не нашёл — о какой сумме идёт речь?– VladD18 июн 2017 в 15:13
-
Пример. Целевая сумма 15, массив [0,1,9,10]. 0 + 1 + 10 слишком мало, 0 + 9 + 10 слишком много. О какой из этих двух сумм идёт речь?– VladD18 июн 2017 в 15:14
-
1@VladD оригинальный ответ использует слова "левая и правая половины". Сравнение с суммой должно было это намерение отразить. Но я уже не уверен. Я оставлю ответ, чтобы люди на те же грабли не нарывались.– jfs18 июн 2017 в 16:55