Учитывая массив целых чисел nums и целое число target, верните индексы двух чисел так, чтобы в сумме они составляли target.
Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.
Вы можете вернуть ответ в любом порядке.
def two_sum(nums, target):
# Create an empty dictionary
num_map = {}
# Iterate through the array
for i, num in enumerate(nums):
# Check if the target minus the current number is in the dictionary
if target - num in num_map:
# If it is, return the indices of the two numbers
return [num_map[target - num], i]
# Otherwise, add the current number and its index to the dictionary
num_map[num] = i
# If no two numbers add up to the target, return an empty list
return []
# Example usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target)) # Output: [0, 1]
В этом решении используется словарь в python для хранения элементов массива в виде ключей и их индексов в виде значений. Затем он перебирает массив, проверяя, есть ли в хеш-таблице дополнение текущего элемента (цель — текущий элемент). Если это так, он возвращает индексы двух элементов. Если никакие два элемента не совпадают с целью, он возвращает пустой список. Это решение имеет временную сложность O(n) и пространственную сложность O(n).
Этот вопрос чаще всего задают в таких компаниях, как Google, Microsoft и Amazon.
Вы можете следить за следующими репозиториями Github, чтобы узнать о других проблемах, которые помогут вам при подготовке к интервью. Удачного кодирования :)
