Я пишу эту серию, чтобы помочь вам на технических собеседованиях и самому научиться лучше программировать.

Давайте начнем!

Постановка задачи

Учитывая массив целых чисел nums и целое число target, верните индексы двух чисел так, чтобы их сумма составляла target.

Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не сможете использовать один и тот же элемент дважды.

Вы можете вернуть ответ в любом порядке.

Сложность

Сложность этой задачи согласно LeetCode — легкая.

Понимание постановки задачи

Если у нас есть массив целых чисел с именем nums как [2,7,11,15] и целое число с именем target, значение которого равно 9, наша цель — вернуть результат [0,1].

Это потому, что nums[0] + nums[1] == 9.

Решения

Начнем с самого интуитивного и неэффективного подхода и будем двигаться к повышению эффективности решения этой проблемы.

1. Подход грубой силы

В этом подходе мы будем использовать два цикла for следующим образом:

def two_sum(nums, target):
    nums_length = len(nums)
    
    for i in range(nums_length):
        for j in range(i + 1, nums_length):
            if nums[i] + nums[j] == target:
                return [i, j]
    
    return []

Мы перебираем все пары чисел в массиве nums и проверяем, равна ли их сумма target.

Временная сложность
O(n²), поскольку используются два вложенных цикла for.

Пространственная сложность
O(1), поскольку дополнительные структуры данных не создаются в соответствии с входным размером, а во время итерации используется постоянный объем пространства.

2. Сортировка и двухточечный подход

В этом подходе мы сначала сортируем массив в порядке возрастания.

Затем мы используем два указателя, называемые left и right, которые указывают на начало и конец массива соответственно.

def two_sum(nums…