Two Sum

Условие задачи (eng)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Условие задачи (rus)

Получив на вход массив целых чисел nums и целевое целое число, вернуть индексы двух элементов массива, в сумме образующих целевое число.

Вы можете предположить, что решение будет всегда единственным, и вы не можете использовать один и тот же элемент дважды.

Вы можете вернуть индексы в любом порядке.

Решение 1: brute force

Для каждого элемента массива перебираем оставшиеся элементы и проверяем, не получится ли в сумме целевое число.

  • Плюсы: для работы алгоритма не нужна доп. память

  • Минусы: сложность алгоритма О(n2), т.к. в реализации присутствует двойной цикл по всему массиву

Развернуть
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return (i, j)

Решение 2: hash maps

Ключ: второй путь заключается в том,

Развернуть
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        cache = {val: i for i, val in enumerate(nums)}
        for i, x in enumerate(nums):
            needle = target - x
            if needle in cache:
                if i != cache[needle]:
                    return (i, cache[needle])