Ошибка в задаче two_sum

Question

Задача:

Вам дан список целых чисел и некоторое целевое число, которое представляет собой сумму двух чисел из этого списка. Напишите функцию two_sum, которая принимает на вход список и число и возвращает индексы тех чисел из списка, сумма которых равна целевому числу. Подразумевается, что задача имеет ровно одно решение. Дважды использовать одно и то же число нельзя. Индексы возвращаются в виде кортежа. Для решения рекомендуется использовать словарь.

Код:

def two_sum(spisok, chislo):
    b = []
    old = []
    for i in spisok:
        for j in spisok:
            if i + j == chislo and i != j and i not in old and j not in old:
                b.append(spisok.index(i))
                b.append(spisok.index(j))
        old.append(i)
    return tuple(b)

Ошибка: Как я уже сказал, неизвестно где неизвестно что, где-то ответ отличается от верного согласно сайту

Answer 1

Первая задачка с leetcode

Идем по списку и добавляем первое слогаемое num в словарь, где ключ текущее число из списка, а значение его индекс.
Если находим слогаемое res, которое уже находится в нашем словаре, возвращаем индексы двух слогаемых.

def twoSum(nums: list[int], target: int) -> tuple[int, int]:
    prev = dict()
    for i, num in enumerate(nums):
        res = target - num
        if res in prev:
            return i, prev[res]
        else:
            prev[num] = i

print(twoSum([2,7,11,15], 9))

Вывод:

(1,0)

UPD

В твоем решении ошибка в условии, т.к например при nums = [2, 2] и target = 4, оно не выполнится.

if i + j == chislo and i != j and i not in old and j not in old:

Далее, поиск индексов затратит дополнительные O(N + N) времени, что можно исправить использовав функцию enumerate

b.append(spisok.index(i))
b.append(spisok.index(j))

Ну и вообщем данный алгоритм затритит в худшем случаи O(N * N) + O(N + N) - времени, что не есть хорошо, когда предложенный алгоритм выше затрит только O(N) - времени.

Исправленная версия:

def two_sum(arr: list[int], target: int) -> tuple[int, int]:
    for i, num1 in enumerate(arr):
        for j, num2 in enumerate(arr):
            if num1 + num2 == target and i != j:
                return i, j

print(two_sum([2,2], 4))

Вывод:

(0,1)

БЛОГ НА HUSL

Ошибка в задаче two_sum

Ответы (1 шт):