Два слагаемых и множество вариантов
Решайте задачи two-sum, three-sum, four-sum и two-sum с отсортированным массивом с помощью хеш-таблиц и двух указателей, сравнивая затраты времени и памяти
«Два слагаемых и множество вариантов» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Задача о двух слагаемых: классическая задача на собеседовании
LeetCode 1 «Два слагаемых»: дан неотсортированный массив и целевое значение; верните индексы двух элементов, сумма которых равна целевому значению. Подход с полным перебором за O(n²) проверяет все пары. Оптимальный подход за O(n) использует хеш-таблицу: для каждого элемента x проверьте, существует ли в таблице target - x. Если да, верните пару индексов. Если нет, сохраните x и его индекс в таблице.
Задача о двух слагаемых часто бывает самой первой задачей на собеседовании — безупречное знание её решения показывает, что Вы готовы перейти к более сложным задачам.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Почему хеш-таблица работает для задачи о двух слагаемых
Хеш-таблица хранит каждый уже встреченный элемент. При обработке элемента x, если target - x находится в таблице, эти два элемента образуют допустимую пару. Важно, что дополняющий элемент всегда проверяется до сохранения x. Это предотвращает случай, когда один элемент объединяется сам с собой (например, если x == target/2, проверка таблицы выполняется до сохранения x, поэтому совпадение возникнет только при наличии двух копий).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iЗадача о двух слагаемых в отсортированном массиве (два указателя)
Если массив уже отсортирован и нужны индексы значений (а не исходные индексы), используйте технику двух указателей: левый и правый указатели начинают движение с противоположных концов. Если сумма равна целевому значению, верните результат. Если сумма слишком мала, сдвиньте левый указатель вправо. Если сумма слишком велика, сдвиньте правый указатель влево. Время работы составляет O(n), а дополнительная память — O(1); это лучше подхода с хеш-таблицей, когда массив отсортирован и память ограничена.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Три слагаемых (LeetCode 15)
LeetCode 15 «Три слагаемых»: найдите все уникальные тройки с суммой, равной нулю. Отсортируйте массив, по очереди фиксируйте один элемент и применяйте метод двух указателей к оставшемуся отсортированному подмассиву. Пропускайте повторяющиеся значения, чтобы избежать одинаковых троек. Время работы: O(n²) — оптимально для этой задачи, поскольку сам результат может содержать O(n²) троек.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Четыре слагаемых (LeetCode 18)
LeetCode 18 «Четыре слагаемых»: найдите все уникальные четвёрки с суммой, равной целевому значению. Расширьте подход для трёх слагаемых: зафиксируйте два элемента с помощью двух вложенных циклов (пропуская повторения), а затем примените два указателя к внутреннему подмассиву. Время работы: O(n³). В общем случае для k слагаемых шаблон заключается в рекурсивной фиксации k-2 элементов с последующим применением двух указателей, что даёт время работы O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Два слагаемых с суммой, наиболее близкой к целевой
Распространённый вариант: найдите пару с суммой, наиболее близкой к целевому значению (она может не совпадать с ним в точности). Отсортируйте массив и используйте два указателя. Отслеживайте ближайшую из найденных сумм и обновляйте результат, когда абсолютная разность с целевым значением становится меньше. Этот подход со временем работы O(n log n) прост после сортировки.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Задача о двух слагаемых с несколькими парами (все пары)
Чтобы найти все пары с суммой, равной целевому значению, отсортируйте массив и используйте два указателя, собирая все пары. После нахождения подходящей пары пропустите повторяющиеся значения с обоих концов, прежде чем продолжить. Это даёт O(n log n) на сортировку и O(n) на проход, то есть O(n log n) в целом. Для сбора пар также можно использовать хеш-таблицу, но при этом нужно внимательно обрабатывать повторения.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Подсчёт пар с суммой меньше K
Другой вариант: подсчитать, сколько пар имеют сумму меньше k. Отсортируйте массив и используйте два указателя. Когда nums[lo] + nums[hi] < k, все пары (lo, lo+1), (lo, lo+2), ..., (lo, hi) допустимы — всего hi - lo пар. Увеличьте левую границу. В противном случае уменьшите правую границу. Общее время работы складывается из O(n log n) на сортировку и O(n) на подсчёт.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyЗадача о двух слагаемых с хеш-таблицей: обработка повторений
Если одно и то же значение может встречаться несколько раз и нужно подсчитать количество подходящих пар (а не только проверить их существование), храните в таблице частоты. Для пар, в которых оба элемента равны, количество пар при частоте f равно f*(f-1)//2. Для пар с различными элементами перемножьте их частоты. Это позволяет подсчитать все подходящие пары за O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Распознавание вариантов шаблона задачи о двух слагаемых
Шаблон задачи о двух слагаемых встречается во многих формах. Распознавайте его, когда задача просит найти два или более элемента, удовлетворяющих числовой зависимости (сумме, произведению, разности). Основная стратегия всегда одна: зафиксировать один элемент, а затем найти дополняющий его элемент в заранее подготовленной структуре (хеш-таблице или отсортированном массиве с указателем). Для перехода к задаче о k слагаемых зафиксируйте k-2 элементов с помощью вложенных циклов и примените базовый случай.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Как рассказывать о задаче о двух слагаемых на собеседовании
Если на собеседовании встречается задача о двух слагаемых, проговаривайте ход рассуждений: «Мне нужны два числа, сумма которых равна целевому значению. Для каждого числа x нужно проверить, существует ли target-x. Я могу ответить на этот вопрос за O(1) с помощью хеш-таблицы, получив общее время O(n) и дополнительную память O(n). Если бы массив был отсортирован, я мог бы использовать два указателя и O(1) дополнительной памяти». Назовите оба подхода и перед выбором спросите, есть ли ограничения по памяти.
Быстрая проверка
Проверьте, насколько хорошо вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке вы узнали: задача о двух суммах использует хеш-таблицу для проверки наличия дополнения за O(1), что даёт O(n) в целом, для отсортированных массивов два указателя обеспечивают O(1) дополнительной памяти, а задачи о трёх и четырёх суммах сводятся к задаче о двух суммах с помощью сортировки и вложенных циклов и выполняются за O(n²) и O(n³) соответственно. Далее мы рассмотрим шаблоны подсчёта частот и группировку с помощью словаря со значениями по умолчанию и счётчика.
Изучай Python с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 30
- Уроки
- 120
Часто задаваемые вопросы
Урок «Два слагаемых и множество вариантов» бесплатный?
Да — полный текст урока «Два слагаемых и множество вариантов» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Два слагаемых и множество вариантов»?
Решайте задачи two-sum, three-sum, four-sum и two-sum с отсортированным массивом с помощью хеш-таблиц и двух указателей, сравнивая затраты времени и памяти Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Два слагаемых и множество вариантов»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Внутреннее устройство хеш-функций и обработка коллизий
- Два слагаемых и множество вариантов
- Подсчёт частот и группировка
- Самая длинная последовательность и кэш LRU