Максимальное количество пар K-суммы

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дан целочисленный массив nums и целое число k.

За одну операцию вы можете выбрать из массива два числа, сумма которых равна k, и удалить их из массива.

Верните максимальное количество операций, которые вы можете выполнить с массивом.

⚠️ Ограничения

— Длина массива находится в диапазоне от 1 до 10^5
— Каждый элемент массива может принимать значение в диапазоне от 1 до 10^9
— k находится в диапазоне от 1 до 10^9

1️⃣ Пример

Входные данные

nums = [1,2,3,4], k = 5

Ответ: 2

Вы можете удалить две пары чисел: (1,4) и (2,3), сумма которых равна 5.

2️⃣ Пример

Входные данные

nums = [3,1,3,4,3], k = 6

Ответ: 1

Вы можете удалить одну пару чисел: (3,3), сумма которых равна 6.


✅ Решение

Для решения задачи мы создадим хеш-таблицу digits, которая будет хранить частоту каждого числа из массива.

Запускаем цикл по всем элементам массива и для каждого числа рассчитываем разность diff между k и текущим числом num.

Если в объекте digits уже есть запись для diff, это означает, что ранее было найдено число, которое в сумме с текущим числом num даст k. Если это так, то уменьшаем количество доступных чисел diff на единицу, и счетчик пар res увеличивается на один, так как найдена новая пара.

Если же такого числа нет, то текущее число num добавляется в digits, увеличивая счетчик количества этого числа на единицу, чтобы в будущем его можно было использовать для создания пары с другим числом.

Таким образом, функция последовательно проверяет каждое число из массива, пытаясь сформировать пары, и возвращает общее количество найденных пар, которые в сумме дают число k.

Посмотреть реализацию в блоге

#arrays #medium