Ссылка: → https://leetcode.com/problems/two-sum/

Проблема:

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

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

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

Ответ:

Теперь нам нужно найти среди всех чисел в массиве два числа, которые при сложении дают нам третье число, равное target.

Например,

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

Может быть два подхода, давайте сначала обсудим простой:

Подход №1

  • Возьмите один элемент
  • Добавьте этот элемент с каждым другим элементом
  • После добавления сравните сумму с заданной целью
  • Если сумма равна цели, вернуть индексы этих двух элементов
  • Если сумма не равна цели, мы проверяем следующую пару

Это выглядит просто, но давайте проанализируем временные и пространственные сложности.

  • Временная сложность

Допустим, в массиве n элементов, тогда -

For 1st element - we will check for (n - 1) elements
For 2nd element - we will check for (n - 2) elements
For 3rd element - we will check for (n - 3) elements 
and so on...

Итак, окончательный результат мы можем получить, как показано ниже.

[(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1]

Теперь, если мы переупорядочим элементы так, чтобы после первого шел последний, затем второй, затем предпоследний

[(n - 1) + 1 + (n - 2) + 2 + (n - 3) + 3 ...]

Теперь вы видите, как упорядочены элементы, что каждая из этих пар равна

[(n - 1 + 1) = n, (n - 2 + 2) = n, ...

Так как элементов n-1, таких пар (n-1)/2.

Итак, вы добавляете n(n-1)/2 раза, так что общее значение равно

N*(N-1)/2.

n * (n — 1) / 2 = n2–2n ≈ n2

Таким образом, наша временная сложность будет — O(n2).

  • Пространственная сложность

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

Подход №2

При анализе задачи мы столкнулись со следующим уравнением

c = a + b

но можем ли мы написать приведенное выше уравнение как -

b = c - a
  • Перебрать массив
  • Проверяем, встречались ли мы с текущим элементом раньше
  • Если у нас есть, мы вернем индекс этого элемента и индекс разницы между target и current element. Раньше мы сталкивались с этим элементом только в том случае, если мы сохранили разницу между target и элементом, который при добавлении к текущему элементу дает сам target.
  • Если нет, мы сохраним разницу между target и current element.
  • Повторите процесс

Поскольку нам нужно хранить наш difference, нам нужна структура данных Map, в которой можно хранить difference и соответствующий ему индекс.

  • Временная сложность

Поскольку мы повторяем массив только один раз, временная сложность будет O(n).

  • Пространственная сложность

Поскольку нам нужна карта размером с массив, сложность пространства будет O(n).

Код (Python):

Надеюсь, вам понравился этот пост. Здесь мы решили самую первую задачу в LeetCode за O(n) время и O(n) пространство.

Спасибо, что прочитали эту статью ❤

Если я что-то не так? Позвольте мне в комментариях. Я хотел бы улучшить.

Хлопайте 👏 Если вам поможет эта статья.