Ссылка: → 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) пространство.
Спасибо, что прочитали эту статью ❤
Если я что-то не так? Позвольте мне в комментариях. Я хотел бы улучшить.
Хлопайте 👏 Если вам поможет эта статья.