Пошаговые инструкции по решению задач с помощью Python
Решение задачи о сумме двух чисел
Задача: дан массив целых чисел nums и целое число target. Требуется найти два числа, сумма которых равна target, и вернуть их индексы. Гарантируется, что ровно одно решение.
Эффективное решение с хеш-таблицей
Вопрос: как найти пару за линейное время, используя дополнительную память?
Используется словарь (хеш-таблица) для хранения встреченных чисел и их индексов. При проходе по массиву для каждого элемента num вычисляется complement = target - num. Если complement есть в словаре, возвращаются индексы текущего элемента и найденного. В противном случае текущий элемент добавляется в словарь.
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) по времени и O(n) по памяти.
Типичные ошибки:
- Использование одного и того же элемента дважды. Проверка
if complement in seen and seen[complement] != iне требуется, так как текущий элемент еще не добавлен в словарь, если он не подходит. - Возврат индексов в неправильном порядке. Обычно требуется сначала меньший индекс – решается указанием
[seen[complement], i]. - Путаница с ключами: в словарь добавляется
numкак ключ, а неcomplement.
Как решить задачу перебором всех пар?
Простейший подход – два вложенных цикла, проверяющих все комбинации. Сложность O(n^2).
def two_sum_bruteforce(nums, target):
n = len(nums)
for i in range(n):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
Пояснение: перебираются все пары i<j. Подходит для маленьких массивов, но неэффективен для больших (n>1000).
Проблемы: медленная работа при больших n; легко допустить ошибку с границами циклов (например, j от i, что приведет к использованию одного элемента дважды).
Как решить задачу с помощью сортировки и двух указателей?
Если индексы не требуются, или их можно восстановить, сначала сортируется массив вместе с индексами. Затем используется два указателя: left и right.
def two_sum_two_pointers(nums, target):
indexed = sorted((num, i) for i, num in enumerate(nums))
left, right = 0, len(nums) - 1
while left < right:
s = indexed[left][0] + indexed[right][0]
if s == target:
return [indexed[left][1], indexed[right][1]]
elif s < target:
left += 1
else:
right -= 1
return []
Сложность O(n log n) из-за сортировки. Этот подход полезен, когда необходимо найти значения, а не индексы, или когда массив уже отсортирован.
Проблемы: теряются исходные индексы, если не сохранить их в пары. Также не подходит, если требуется найти все пары (тогда один указатель может двигаться неправильно).
Как использовать множество для проверки существования пары?
Если нужно только проверить, существует ли пара (без индексов), можно обойтись множеством.
def two_sum_exists(nums, target):
seen = set()
for num in nums:
if target - num in seen:
return True
seen.add(num)
return False
Множество обеспечивает O(1) проверку вхождения. Этот вариант экономит память (только ключи) и подходит для задач, где не нужны индексы.
Ошибка: неверный порядок – сначала добавить элемент в множество, а потом проверять, что приведет к использованию одного и того же числа. Правильно – сначала проверять, потом добавлять.
Расширенные примеры и оптимизация
Пример 1: поиск всех пар с заданной суммой (с дубликатами)
Задача: найти все уникальные пары чисел (значения, не индексы), сумма которых равна target. Массив может содержать дубликаты.
def find_all_pairs(nums, target):
from collections import Counter
freq = Counter(nums)
pairs = []
for num, count in freq.items():
complement = target - num
if complement in freq:
if num == complement and count >= 2:
pairs.append((num, num))
elif num < complement:
pairs.append((num, complement))
return pairs
Результат для nums = [1,2,3,2,4], target=5:
[(1,4), (2,3)]
Пояснение: используем Counter для подсчета частот. Проверяем только num <= complement, чтобы избежать дублирования пар.
Пример 2: задача Three Sum (сумма трех чисел равна нулю)
Дан массив, найти все уникальные тройки, дающие в сумме 0. Используется сортировка и два указателя для фиксированного первого элемента.
def three_sum(nums, target=0):
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 == target:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left-1]:
left += 1
while left < right and nums[right] == nums[right+1]:
right -= 1
elif s < target:
left += 1
else:
right -= 1
return result
Сложность O(n^2). Важно избегать дубликатов, пропуская одинаковые значения соседних элементов.
Пример 3: Two Sum с использованием однопроходного словаря и возвратом всех индексов
Если массив содержит несколько решений, можно собрать все пары индексов.
def all_two_sum_indices(nums, target):
indices = {}
result = []
for i, num in enumerate(nums):
complement = target - num
if complement in indices:
for j in indices[complement]:
result.append([j, i])
indices.setdefault(num, []).append(i)
return result
Результат для [1,2,3,2,1,4] и target=5:
[[0,5], [1,2], [3,2]]
Пояснение: словарь хранит список индексов для каждого числа. Каждый раз, когда встречается complement, создаются пары со всеми предыдущими индексами.
Пример 4: работа с большими потоками данных (генератор)
Если данные поступают в виде потока (например, из файла или сети), можно обрабатывать их без загрузки в память. Решение с множеством позволяет проверять пары на лету.
def streaming_two_sum(stream, target):
seen = set()
for num in stream:
if target - num in seen:
return True
seen.add(num)
return False
Этот подход не требует хранения всего массива, память O(k), где k – количество уникальных чисел, до встречи решения.
Пример 5: использование библиотеки numpy для векторизации
Для больших массивов, когда производительность критична, можно использовать numpy.
import numpy as np
def two_sum_numpy(nums, target):
arr = np.array(nums)
# Создаем матрицу сумм (затратно по памяти)
sums = arr[:, None] + arr[None, :]
i, j = np.where(np.triu(sums, k=1) == target)
return i[0], j[0]
Этот способ использует broadcasting и может быть быстрее для огромных массивов (но требует много памяти).
Пример 6: оптимизация для частого поиска в одном массиве
Если один и тот же массив используется для множества запросов, выгодно предварительно построить хеш-таблицу значений–индексов.
class TwoSumFinder:
def __init__(self, nums):
self.num_to_indices = {}
for i, num in enumerate(nums):
self.num_to_indices.setdefault(num, []).append(i)
def find(self, target):
for num, indices in self.num_to_indices.items():
complement = target - num
if complement in self.num_to_indices:
if num != complement:
return [indices[0], self.num_to_indices[complement][0]]
else:
if len(indices) >= 2:
return [indices[0], indices[1]]
return None
Построение таблицы O(n), каждый запрос O(1) в среднем, если первое же число даёт решение.