Решён
Напишите оптимальный Python код для задачи

Денис Воганов • Python •
3.5k
5

Нужно написать функцию которая принимает список чисел и возвращает все пары чисел сумма которых равна заданному числу.

Например:

find_pairs([1, 2, 3, 4, 5], 6)

Должно вернуть: [(1, 5), (2, 4)]

Мой код работает но преподаватель сказал что он неоптимальный. Вот что я написал:

def find_pairs(nums, target):
    result = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                result.append((nums[i], nums[j]))
    return result

Как сделать оптимальнее?

PythonАлгоритмыЗадачиКод-ревьюОптимизация

5 ответов

Лучшие Новые Старые
Решение
45
Участник • 4 ответа

Твое решение имеет сложность O(n²) из-за вложенных циклов. Для больших списков это медленно.

Оптимальный подход - использовать множество (set) для поиска комплементарного числа за O(1):

def find_pairs(nums, target):
    seen = set()
    pairs = set()
    for num in nums:
        complement = target - num
        if complement in seen:
            pair = tuple(sorted((num, complement)))
            pairs.add(pair)
        seen.add(num)
    return list(pairs)

Сложность O(n) по времени, O(n) по памяти.

Что тут происходит:

  1. Идем по списку один раз
  2. Для каждого числа вычисляем сколько нужно чтобы получить target
  3. Проверяем есть ли это число среди уже просмотренных
  4. Добавляем текущее число в множество просмотренных

Множество pairs нужно чтобы не было дубликатов. sorted() - чтобы (1,5) и (5,1) считались одной парой.

Аватар Денис Воганов
Денис Воганов Автор

О, круто! Про set я знаю но не додумался так применить. Спасибо!

18
Участник • 1 ответ

А зачем вообще оптимизировать? Если список маленький - разницы не будет никакой. Твой код читается лучше чем все эти трюки с сетами.

Преждевременная оптимизация - корень всех зол (c) Кнут.

Если препод просто придирается - покажи ему версию с set. Если это реальная задача - сначала измерь насколько твой код медленный. Может он и так достаточно быстрый.

Аватар Самоучка Макс
Самоучка Макс

Не согласен. На учебных задачах как раз и надо учиться писать оптимально. А то потом в проде пишут O(n³) и удивляются почему все тормозит.

12
Эксперт • 5 ответов

Если нужен однострочник (но читаемость страдает):

find_pairs = lambda nums, t: list({tuple(sorted((n, t-n))) for n in nums if t-n in set(nums[:nums.index(n)])})

Не советую так писать в проде, но на собесах иногда спрашивают.

21
Участник • 1 ответ

Классическая задача Two Sum, только с возвратом всех пар а не индексов.

Почитай на LeetCode объяснения к задаче #1 (Two Sum), там куча вариантов решения с разбором сложности: https://leetcode.com/problems/two-sum/

8
Участник • 3 ответа

еще вариант через словарь если нужны индексы:

def find_pairs_idx(nums, target):
    num_to_idx = {}
    res = []
    for i, n in enumerate(nums):
        if target - n in num_to_idx:
            res.append((num_to_idx[target-n], i))
        num_to_idx[n] = i
    return res

но если индексы не нужны то с сетом проще как выше написали

Написать ответ

Визуальный редактор (WYSIWYG)
Премодерация гостей

Вы отвечаете как гость. Ваш ответ будет скрыт до проверки модератором. Чтобы ответ появился сразу и вы получали репутацию — войдите в аккаунт.

Или войдите в систему
Будьте вежливы и соблюдайте правила платформы.