Ссылка на 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 г.
