Постановка задачи
Учитывая массив целых чисел nums и целое число target, верните индексы двух чисел так, чтобы их сумма равнялась target.
Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Вы можете возвращать ответ в любом порядке.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Подход 1
Итерацией пройдитесь по массиву, выберите каждый элемент и проверьте, существует ли в оставшемся массиве какой-либо другой элемент, который при сложении с первым дает целевое значение. Гарантируется, что одна такая пара существует. Поэтому нам нужно вернуть их индексы.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i,j]
return [-1, -1]
Временная сложность — O(n^2) — из-за вложенных циклов for.
Пространственная сложность — O(1).
Подход 2
Итерация по массиву и проверка для каждого элемента, есть ли в хэшмапе число, необходимое для суммирования с целью. Если есть, возвращаем массив с обоими его индексами. В противном случае добавьте текущий элемент в hashmap с его индексом в качестве значения и элементом в качестве ключа.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashMap = {}
for i in range(len(nums)):
if target - nums[i] in hashMap: # If present in hashmap
return [hashMap[target-nums[i]], i]
else:
hashMap[nums[i]] = i # Add item as key and index as value into hashmap
return [-1, -1]
Заключение
Дайте мне знать, если я упустил какой-либо другой подход.
Следите за мной, чтобы получить больше подобных объяснений.
Давайте общаться: Twitter LinkedIn Showwcase