Контест Middle Массивы и хеш-таблицы спрашивают часто обновлено
Число пар с заданной суммой
Условие
Дан массив из n целых чисел и число X. Посчитайте количество пар индексов i < j, для которых aᵢ + aⱼ = X.
Ввод: в первой строке n и X (1 ≤ n ≤ 2500, |X| ≤ 2·10⁹), во второй n чисел (|aᵢ| ≤ 10⁹).
Вывод: одно число: количество пар.
Пример 1
Ввод:
5 6
1 5 3 3 7
Вывод:
2
Пример 2
Ввод:
4 0
0 0 0 0
Вывод:
6
Как подойти
Подсказки: 2
- Для каждого aⱼ вам нужно знать, сколько раз раньше встречалось X − aⱼ.
- Число пар растёт квадратично: держите счётчик в 64-битном типе.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.