Ссылка на Leetcode: https://leetcode.com/problems/two-sum/

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

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

Given nums = [2, 7, 11, 15], target = 9, 
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

Метод 1: грубая сила

Как и в случае любой проблемы, мы всегда начинаем с метода грубой силы. Каков самый простой способ получить ответ, не заботясь о временной сложности и т. д.?

Мы можем просто использовать 2 цикла for и узнать индексы:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        results = []
        for num1 in nums:
            for num2 in nums:
                if(num1 + num2 == target):
                    results.append(num1)
                    results.append(num2)
                    
        return results

Это даст нам правильные результаты, но такой метод будет плохим решением для огромного массива. Хотя пространственная сложность находится в постоянном времени O (1), с двумя циклами for мы имеем временную сложность O (n 2).

Способ 2: хеширование

Чтобы оптимизировать наше решение, мы просто используем хеш-таблицу или словарь. Мы обмениваем пространство на время.

Мы храним числа в массиве как ключи, а индексы — как соответствующие значения. Каждый раз мы проверяем, существует ли в хеш-таблице дополнение числа (т. е. target - number). Если да, то мы нашли пару! В противном случае мы добавляем его в хеш-таблицу.

Код будет выглядеть так:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if(complement in num_map):
                return [i, num_map[complement]]
            else:
                num_map[nums[i]] = i
        return []

Это имеет временную сложность всего O (n), так как мы проходим по списку только один раз. Пространственная сложность O(n) существует, поскольку нам нужна хеш-таблица для хранения чисел.

Первоначально опубликовано на https://rightfrombasics.com 25 января 2020 г.