Как найти все пары чисел с заданной суммой в списке: методы и код
Поиск пар чисел с заданной суммой в списке
Как быстро найти пары чисел, сумма которых равна заданному значению?
Наиболее эффективное решение использует хэш-таблицу (множество или словарь) для отслеживания уже встреченных чисел. Алгоритм проходит по списку один раз (сложность O(n)). Для каждого числа num вычисляется дополнение target - num. Если дополнение уже есть в множестве, то найдена пара.
def find_pairs_hash(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
задачи с кодом python (задачи с кодом на python)
Результат для nums = [2, 7, 11, 15] и target = 9 будет [(2, 7)].
Типичные проблемы: Если список содержит дубликаты, то для одного числа может быть найдено несколько пар, но при этом один и тот же элемент может быть использован дважды, если он встречается дважды. В данном решении каждый элемент используется только один раз, так как сначала проверяется наличие дополнения, а затем добавляется текущее число. Это исключает повторное использование одного и того же элемента. Если требуется учитывать все комбинации, даже с повторным использованием элементов (например, если список содержит одинаковые числа), можно изменить логику.
Как перебрать все возможные пары с помощью двух циклов?
Простой, но медленный подход: для каждого элемента проверяем все последующие. Сложность O(n^2). Подходит для маленьких списков.
def find_pairs_bruteforce(nums, target):
pairs = []
n = len(nums)
for i in range(n):
for j in range(i+1, n):
if nums[i] + nums[j] == target:
pairs.append((nums[i], nums[j]))
return pairs
Python практические задачи (практические задачи на python)
Частые ошибки: Вложенный цикл может привести к большому времени выполнения при списках более нескольких сотен элементов. Также возможно появление дублирующих пар, если в списке есть одинаковые числа, но это решается явной проверкой индексов.
Как использовать сортировку и метод двух указателей?
Сначала отсортировать список (сложность O(n log n)), затем использовать два указателя: один в начале, другой в конце. Если сумма меньше target, сдвигаем левый указатель; если больше – правый; если равна – записываем пару и сдвигаем оба. Этот подход находит все пары, но теряет исходные индексы, если они важны. Сложность O(n log n).
def find_pairs_two_pointers(nums, target):
nums.sort()
pairs = []
left, right = 0, len(nums)-1
while left < right:
s = nums[left] + nums[right]
if s == target:
pairs.append((nums[left], nums[right]))
left += 1
right -= 1
elif s < target:
left += 1
else:
right -= 1
return pairs
Возможные трудности: Сортировка изменяет исходный список. Если нужно сохранить исходный порядок, следует работать с копией. Также при наличии дубликатов могут быть получены повторяющиеся пары, если не учитывать, что одинаковые значения встречаются несколько раз. Можно добавить условие, чтобы пропускать повторяющиеся значения после нахождения пары.
Дополнительные примеры и расширенные сценарии
Пример 1: Возврат индексов первой пары (классическая Two Sum)
def two_sum_indices(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Пример nums = [2, 7, 11, 15] target = 9 print(two_sum_indices(nums, target)) # [0, 1]
Пример 2: Все уникальные пары значений (каждый элемент используется один раз)
from collections import defaultdict
def all_pairs_unique(nums, target):
count = defaultdict(int)
pairs = set()
for num in nums:
complement = target - num
if count[complement] > 0:
pairs.add(tuple(sorted((complement, num))))
count[complement] -= 1
else:
count[num] += 1
return list(pairs)
# Пример со повторяющимися числами nums = [1, 1, 2, 2, 3, 4, 5, 5] target = 6 print(all_pairs_unique(nums, target)) # [(1, 5), (2, 4), (3, 3)]
Пример 3: Генератор, выдающий пары по мере нахождения
def pair_generator(nums, target):
seen = set()
for num in nums:
complement = target - num
if complement in seen:
yield (complement, num)
seen.add(num)
# Использование
for pair in pair_generator([2, 7, 4, 5, 3], 7):
print(pair) # (2, 5), (4, 3)
Пример 4: Обработка пустого списка и отсутствия пар
def safe_find_pairs(nums, target):
if not nums:
return []
seen = set()
pairs = []
for num in nums:
complement = target - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
print(safe_find_pairs([], 10)) # [] print(safe_find_pairs([1,2,3], 100)) # []
Пример 5: Использование itertools.combinations для полного перебора
import itertools
def all_combinations_pairs(nums, target):
pairs = []
for a, b in itertools.combinations(nums, 2):
if a + b == target:
pairs.append((a, b))
return pairs
print(all_combinations_pairs([2,7,11,15], 9)) # [(2,7)]