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