Яндекс задания по Python: разбор и практические советы
Как найти два элемента с заданной суммой за линейное время
Задания от Яндекса по Python нередко включают классическую задачу: дан массив целых чисел и целевая сумма, требуется найти два элемента (их индексы), сумма которых равна этой сумме. Рассмотрим несколько подходов с акцентом на эффективность и типичные ошибки.
Наиболее эффективное решение: использование словаря (хэш-таблицы). Алгоритм проходит по массиву один раз, сохраняя каждый элемент и его индекс. Для текущего числа num вычисляется complement = target - num. Если complement уже есть в словаре, значит искомая пара найдена. Время работы O(n), память O(n).
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
яндекс задания python (задания от яндекса по python)
Пояснение: на каждой итерации мы проверяем, существует ли уже число, которое дополнит текущее до суммы. Если да, возвращаем индексы. Если нет, записываем текущее число в словарь. После окончания цикла возвращаем пустой список.
Какое решение подойдет для очень маленьких массивов
Простой перебор всех пар. Вложенные циклы дают O(n^2). Код короткий, но медленный на больших данных.
def two_sum_bruteforce(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
Python разработчик тестовые задания (примеры тестовых заданий python)
Применение: если заранее известно, что массив содержит не более 100 элементов, такой вариант допустим.
Как найти пару, если массив уже отсортирован
Метод двух указателей. Предварительно сортируем массив, сохраняя исходные индексы (чтобы вернуть их, а не значения). После сортировки двигаем указатели с обоих концов к середине. Сложность O(n log n) на сортировку, память O(n).
def two_sum_two_pointers(nums, target):
indexed = sorted(enumerate(nums), key=lambda x: x[1])
left, right = 0, len(nums) - 1
while left < right:
current_sum = indexed[left][1] + indexed[right][1]
if current_sum == target:
return [indexed[left][0], indexed[right][0]]
elif current_sum < target:
left += 1
else:
right -= 1
return []
Важно: после сортировки индексы элементов перемешиваются, поэтому мы используем enumerate для сохранения исходных позиций.
Типичные ошибки и их предотвращение:
- Не учтен случай, когда complement равен текущему числу, и это число встречается только один раз. Решение: в словаре проверяем наличие до добавления текущего элемента, поэтому дубликат не будет найден, а если число действительно образует пару с самим собой (например, target = 2 * num и num встречается дважды), то при втором вхождении оно найдёт первое.
- Возврат индексов в неправильном порядке. Код возвращает сначала индекс меньшего элемента? В решении со словарём порядок такой, как они найдены (сначала меньший индекс у complement, потом текущий). Для двух указателей после сортировки порядок может быть любым.
- Забыли обработать случай отсутствия пары: возвращаем пустой список.
- Игнорирование возможности нескольких пар - базовый код возвращает только первую.
Расширенные примеры для задачи суммы двух чисел
Ниже приведены варианты, расширяющие базовое решение.
Нахождение всех уникальных пар (без повторения индексов)
Если требуется вернуть все пары значений (не индексов), которые в сумме дают target, используется множество для хранения уже просмотренных элементов. При этом каждая пара выводится только один раз (например, для [3,3] с target=6 будет одна пара (3,3)).
def find_all_pairs(nums, target):
seen = set()
pairs = []
for num in nums:
complement = target - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
print(find_all_pairs([1,2,3,4,5,6,7,8,9], 10))
[(1, 9), (2, 8), (3, 7), (4, 6)]
Обратите внимание: пара (5,5) не появилась, так как 5 встречается только один раз, и её complement тоже 5, но в множестве ещё нет 5 при первом проходе.
Использование словаря для возврата индексов всех пар
Чтобы получить все индексы, можно хранить для каждого значения список индексов.
def two_sum_all_indices(nums, target):
index_map = {}
result = []
for i, num in enumerate(nums):
complement = target - num
if complement in index_map:
for j in index_map[complement]:
result.append((j, i))
index_map.setdefault(num, []).append(i)
return result
print(two_sum_all_indices([1,5,5,3,6,2,4], 10))
[(1, 4), (2, 4)] # индексы: 1:5, 4:6 и 2:5, 4:6
Работа с большими массивами и отрицательными числами
Алгоритм со словарём корректно работает с любыми целыми числами, включая отрицательные. Пример:
nums = [-3, 7, -1, 2, 0, -4]
target = -3
print(two_sum(nums, target))
[0, 4] # -3 + 0 = -3
Двухуказательный метод также поддерживает отрицательные числа, главное - правильная сортировка.
Решение задачи с несколькими суммами (например, три числа)
Иногда в заданиях Яндекса требуется найти три числа, сумма которых равна нулю. Это расширение подхода с двумя указателями: фиксируем одно число и ищем пару с суммой -fixed в оставшейся части массива. Пример для трёх чисел:
def three_sum_zero(nums):
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return result
print(three_sum_zero([-1,0,1,2,-1,-4]))
[[-1, -1, 2], [-1, 0, 1]]
Этот код часто встречается в задачах Яндекса на средний уровень.