0

Задача:

Вам дан список целых чисел и некоторое целевое число, которое представляет собой сумму двух чисел из этого списка. Напишите функцию 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)

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

2
  • Пример входных данных и выходных данных?
    – vlados155
    Commented 30 янв. в 15:57
  • Пример: целевая сумма 2, список [1, 1]. Ожидаемый ответ: (0, 1). Ваша программа вернёт пустой кортеж - ошибка. Commented 30 янв. в 17:29

1 ответ 1

3

Первая задачка с 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)
0

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.