«Один LC в день снижает безработицу».

Вопрос №1:

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

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

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

Пример 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Мое решение:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = []
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if target == nums[i]+nums[j]:
                    indices.append(i)
                    indices.append(j)
                    return indices

Улучшения:

  1. Вместо создания списка и добавления индексов я мог бы просто вернуть индексы во время итерации, что помогло бы уменьшить сложность пространства.
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]

Единственное используемое пространство — это пространство, необходимое для хранения индексов двух чисел. Это пространство является постоянным, независимо от размера массива.

2. Временную сложность можно было бы улучшить, просто используя один цикл для решения этой задачи, например:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict={}
        for i,n in enumerate(nums):
            if n in dict:
                return dict[n],i
            else:
                dict[target-n]=i

Функция сначала создает словарь, который сопоставляет каждое число в массиве с его индексом. Это позволяет функции быстро проверить, был ли уже замечен номер.

Затем функция перебирает массив, начиная с первого элемента. Для каждого элемента функция проверяет, находится ли в словаре дополнение к элементу (целевое значение минус элемент). Если да, то функция нашла два числа, сумма которых равна целевому значению. Функция возвращает индексы этих двух чисел.

В противном случае функция добавляет текущий индекс в словарь, сопоставляя его с дополнением текущего элемента. Это гарантирует, что функция найдет два числа, если они встретятся позже.

Если функция достигает конца массива и не находит двух чисел, которые в сумме соответствуют целевому значению, она возвращает пустой список.

Как видите, второе решение использует больше места, поскольку использует хеш-таблицу. Хэш-таблица — это структура данных, в которой элементы хранятся таким образом, чтобы их можно было быстро найти. Это полезно в задаче о двух суммах, поскольку позволяет нам быстро найти индекс элемента в массиве. Однако хеш-таблица также занимает больше места, чем другие структуры данных, например массив.

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