Поиск пары с заданной суммой
Работайте быстрее полного перебора за O(n^2)
«Поиск пары с заданной суммой» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Задача о сумме пары
Дан массив и целевое значение. Найдите два значения, которые в сумме дают это значение. Это одна из самых распространённых разминочных задач на соревнованиях. 🔍
Метод полного перебора
Очевидное решение перебирает каждую пару с помощью двух вложенных циклов. Оно работает, но проверка всех пар занимает O(n^2) и может оказаться слишком медленной.
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)Где полный перебор не справляется
При n около 100000 сложность O(n^2) означает десять миллиардов проверок, и Вы получите TLE. Ограничения подсказывают, что нужно найти более быстрое решение.
Сначала sort, затем проход
Если сначала выполнить sort для массива, два указателя с обоих концов решат задачу за один проход. Сортировка занимает O(n log n), а затем проход — O(n).
a.sort()
left, right = 0, len(a) - 1Сравнение с целевым значением
На каждом шаге вычисляйте a[left] + a[right]. Это единственное число без каких-либо догадок определяет Ваш следующий шаг.
total = a[left] + a[right]Точное совпадение: готово
Если сумма равна целевому значению, Вы нашли нужную пару. Сразу верните её, поскольку требуется только один подходящий ответ.
if total == target:
return (left, right)В противном случае скорректируйте указатели
Если сумма слишком мала, сдвиньте левый указатель вправо; если слишком велика — правый указатель влево. Отсортированный порядок гарантирует, что каждый сдвиг приближает Вас к цели.
elif total < target:
left += 1
else:
right -= 1Пары не существует
Если указатели пересеклись, не найдя совпадения, подходящей пары не существует. Завершение цикла само по себе является полным ответом.
Альтернатива с хеш-множеством
Если необходимо сохранить исходные индексы, хеш-множество будет удобнее: для каждого значения проверяйте, встречалось ли раньше целевое значение минус это значение.
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)Выбор метода
Используйте два указателя, если массив отсортирован или его можно отсортировать; используйте хеш-множество, если нужна настоящая сложность O(n) без сортировки или необходимо сохранить индексы.
Следите за дубликатами
Если значение может образовать пару с самим собой, убедитесь, что два индекса различаются. Простая проверка left != right или i != j поможет избежать этой ошибки.
Быстрая проверка
Вы хотите превзойти полный перебор O(n^2) при поиске пары с заданной суммой.
Повторение
Отсортируйте массив, а затем выполните проход с помощью двух указателей, чтобы найти нужную пару за O(n log n), или используйте хеш-множество за O(n), если важны индексы. Выбирайте подход с учётом ограничений. ✅
Часто задаваемые вопросы
Урок «Поиск пары с заданной суммой» бесплатный?
Да — полный текст урока «Поиск пары с заданной суммой» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Поиск пары с заданной суммой»?
Работайте быстрее полного перебора за O(n^2) Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Поиск пары с заданной суммой»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Два указателя в отсортированном массиве
- Поиск пары с заданной суммой
- Удаление дубликатов на месте
- Слияние двух отсортированных последовательностей