🧩 Условие задачи
Ссылка на задачу: https://leetcode.com/problems/max-number-of-k-sum-pairs
You are given an integer array nums and an integer k.
In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.
Return the maximum number of operations you can perform on the array.
По-русски:
Дан массив целых чисел nums и целое число k.
За одну операцию можно выбрать два числа из массива, сумма которых равна k, и удалить их.
Нужно вернуть максимальное количество таких операций.
Пример 1:
Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.
Пример 2:
Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
Перед тем как посмотреть решение, подумайте как бы вы решали такую задачу?
Подписывайтесь на мой канал в Телеграмм, чтобы ничего не пропустить.
Ну или на канал в VK, если хотите видеть новые статьи у себя в ленте.
Пример для всех решений (будем на нем разбирать):
nums = [1, 2, 3, 4, 3, 2, 1]
k = 5
Ожидаемый результат:
- Пары: (1,4), (2,3), (2,3)
- Всего: 3 операции
🧠 Решение 1. Хеш-таблица (жадный подход)
📖 Идея:
- Проходим по массиву.
- Для каждого числа num ищем k - num в словаре.
- Если нашли — это пара, увеличиваем счётчик и уменьшаем количество k - num.
- Если не нашли — добавляем num в словарь.
⏱ Сложность:
- Время: O(n)
- Память: O(n)
✅ Пример кода:
или чуть более лаконично, но может чуть менее понятно (но по факту то же самое):
🔍 Пошагово:
✅ Ответ: 3 пары
🚀 Решение 2. Сортировка + два указателя
📖 Идея:
- Сортируем массив.
- Ставим два указателя: один в начале, другой в конце.
- Если сумма равна k — нашли пару, сдвигаем оба.
- Если меньше — сдвигаем левый.
- Если больше — сдвигаем правый.
⏱ Сложность:
- Время: O(n log n) (из-за сортировки) - теоретически медленнее первого решения.
- Память: O(1)
✅ Пример кода:
🔍 Пошагово:
После сортировки:
nums = [1, 1, 2, 2, 3, 3, 4]
start = 0, end = 6
✅ Ответ: 3 пары
⚡ Решение 3. Counter + частотный подсчёт
📖 Идея:
- Считаем, сколько раз встречается каждое число (Counter).
- Для каждого уникального x ищем y = k - x.
- Если x == y, то можно взять count[x] // 2 пар.
- Если x < y, то берём min(count[x], count[y]) пар.
⏱ Сложность:
- Время: O(n) (теоретически как у первого решения)
- Память: O(n)
✅ Пример кода:
🔍 Пошагово:
Counter({1: 2, 2: 2, 3: 2, 4: 1})
✅ Ответ: 1 + 2 = 3 пары
😈 Решение 4. «Хакерский» трюк с подменой времени
📖 Что делает:
Некоторые участники добавляют в конец кода вот такую строчку:
__import__("atexit").register(lambda:open("display_runtime.txt","w").write("0"))
Например вот "самое быстрое решение":
По факту это решение с двумя указателями и сортировкой, которое теоретически менее быстрое чем решение 1 и 3.
Так вот, эта строчка (с импортом), не влияет на алгоритм, но может исказить измерение времени выполнения на платформе (например, LeetCode).
❗ Почему это «хак»?
- Это не ускоряет алгоритм.
- Это просто записывает "0" в файл, который может использоваться системой для анализа времени.
- Такое решение может несправедливо попасть в топ по скорости, хотя по сути оно такое же, как и другие.
⚠️ Вывод:
Не стоит использовать такие трюки — они не улучшают алгоритм, а только искажают статистику.
Спасибо, что прочли до конца 🙌
Подписывайтесь на мой канал в Телеграм или в VK — впереди ещё много интересного про ИИ, NLP и тестирование!
До встречи в следующих статьях! 💡