Один из десятка тысяч разборов этой задачи, в большей степени перевод leetcode, очень недалёкий, но кому-то как и мне может надо прорешать задачу N раз, чтобы понять и не забывать её.
Дано: задан массив целых чисел nums и целое число target, верните индексы двух чисел массива nums сумма которых равна target.
Уточнения:
- задача имеет только одно верное сочетание индексов,
- нельзя использовать один и тот же индекс,
- расположение индексов в ответе не принципиально.
Ограничения:
- 2 <= nums.length <= 10^2,
- -10^9 <= nums[i] <= 10^9,
- -10^9 <= target <= 10^9
Пример:
Дано: nums = [1,16 34,65], target = 66
Ответ: [0,3]
Объяснение: Сумма чисел nums[0] + nums[1] == 9, в ответе мы возвращаем их индексы, записанные в массив: [0, 1].
Решение(Python):
1а)Наивное решение (перебор)
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[j] == target - nums[i]:
return [i, j]
***Проходим первым циклом массив nums, и для каждого элемента массива вторым циклом сравниваем его со всеми остальными значениями массива, если их сумма равна target, выдаём ответ.
Временная сложность: цикл в цикле дают нам сложность O(n)*O(n)
Пространственная сложность: не используется дополнительной памяти, поэтому O(1).
1б) Перебор через списковое включение (list comprehension)
def twoSum(self, nums: List[int], target: int) -> List[int]:
return next((i, j) for i, x in enumerate(nums) for j, y in enumerate(nums[i+1:], i+1) if x + y == target)
***Во внешнем цикле for i, x in enumerate(nums)) выполняется итерация по элементам списка nums с помощью функции enumerate. Переменная внешнего цикла i представляет собой индекс, а x - элемент с этим индексом. Внутренний цикл также использует метод enumerate, но начинает работу с индекса i+1. Переменная j внутреннего цикла представляет собой индекс второго числа, а y - второе число, находящийся под этим индексом. Условие if x + y == target проверяет, равна ли сумма текущих элементов x и y заданному значению, метод next выводит значение полученного объекта.
Временная сложность: цикл в цикле дают нам сложность O(n)*O(n) Пространственная сложность: не используется дополнительной памяти, поэтому O(1).
2а) C использованием дополнительной памяти - хэш таблицы
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
hashmap[nums[i]] = i
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap and hashmap[complement] != i:
return [i, hashmap[complement]]
1)первым циклом, добавляем в хэш-таблицу (hashmap) значение каждого элемента в качестве ключа nums[i] и его индекс i в качестве значения .
2)вторым циклом проверяем, существует ли в хеш-таблице второе число complement дающее в в сумме target (target-nums[i]). Если оно существует и не равно первому числу, то выдаём ответ.
Временная сложность: 2 цикла дают нам сложность O(n) +O(n) = O(n) Пространственная сложность: используем хэш-таблицу hashmap, которая может хранить до N элементов, то есть получаем O(n)
2б) C использованием дополнительной памяти - хэш таблицы - улучшенная версия.
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap:
return [i, hashmap[complement]]
hashmap[nums[i]] = i
Предыдущая версия помогает легче понять текущее решение: записываем в хэш таблицу разность target и текущего элемента цикла, которое соответственно должно быть равно второму числу, которое будет искаться дальше в цикле, когда пара находится, выдаём ответ.
Временная сложность: цикла даёт сложность O(n)
Пространственная сложность: используем хэш-таблицу hashmap, которая может хранить до N элементов, то есть получаем O(n)
2в) C использованием дополнительной памяти - хэш таблицы - улучшенная версия 2.
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap={}
for i,n in enumerate(nums):
if n in hashmap:
return hashmap[n],i
else:
hashmap[target-n]=i
Аналогично с использованием функции enumerate.
Временная сложность: цикла даёт сложность O(n)
Пространственная сложность: используем хэш-таблицу hashmap, которая может хранить до N элементов, то есть получаем O(n)
Ресурсы: leetcode, stackoverflow