Задача двух сумм — Leetcode
Постановка задачи
Предположим, вам дан массив целых чисел и целевая сумма, верните индексы двух чисел в массиве так, чтобы их сумма составляла заданную цель. Вы можете предположить, что каждый вход будет иметь ровно одно решение. Кроме того, вы не можете использовать один и тот же элемент дважды. Вы можете вернуть ответ в любом порядке
Примеры
Пример 1:
Input: nums = [7,2,13,11], target = 9 Output: [0,1]
Пример 2:
Input: nums = [7,3,5], target = 8 Output: [1,2]
Решения
Давайте сначала попытаемся понять постановку задачи. Здесь нам дан массив целочисленных элементов и целевая сумма. Мы должны написать алгоритм, который возвращает индексы двух элементов в этом массиве так, чтобы при сложении этих двух элементов он был равен заданной целевой сумме.
Например, в примере 1 [7,2,13,11] — это заданный массив и заданная целевая сумма = 9. Если мы посмотрим на данный массив, пара, которая добавляется к целевая сумма 9 равна (7,2), т.е. 7+2 = 9. Таким образом, наш алгоритм должен вернуть (0,1) в качестве результата, поскольку это индексы элементов 7 и 2 соответственно в данном массиве.
Аналогично для массива в примере 2 [7,3,5] выводится значение (1,2), поскольку это индексы элементов 3 и 5 соответственно, которые в сумме дают целевую сумму 8.
Примечание. Если таких пар несколько, нам нужно вернуть индексы первой пары слева.
В условии задачи указано, что мы можем возвращать индексы в любом порядке. Давайте разберемся в этом на первом примере. Выходные данные для этого примера — [0,1], поэтому, когда в условии задачи говорится, что мы можем возвращать индексы в любом порядке, это означает, что мы можем вернуть либо [0,1], либо [1,0] в качестве наших выходных данных, оба будут считаться правильными. То же самое и со вторым: мы можем вернуть либо [1,2], либо [2,1].
Решение 1: грубая сила
Простое решение этой проблемы — проверить каждую возможную пару, присутствующую в данном массиве.
Для данного входного массива nums нам необходимо выполнить следующие шаги:
- Запустите два цикла и проверьте каждую комбинацию в данном массиве.
- Зафиксируйте внешний цикл по определенному индексу и переместите внутренний цикл, чтобы получить все возможные пары. Внешний цикл выполняется от i=0 до i=n-2, а внутренний цикл — от j=i+1 до j=n-1.
- На каждой итерации внутреннего цикла проверяйте, составляют ли суммы, представленные индексами внешнего и внутреннего цикла, целевую сумму.
- Если nums[outerLoopIndex] + nums[innerLoopIndex] равно целевому значению, верните [outerLoopIndex ,innerLoopIndex] в качестве результата. В противном случае продолжите итерацию, чтобы проверить наличие следующей пары.
- Повторяйте вышеуказанные шаги, пока не найдете комбинацию, соответствующую заданной цели.
Например, для массива [7,2,13,11] и целевой суммы 24 мы фиксируем внешний цикл с индексом i=0, то есть элементом 7, и проверяем его со всеми возможными значениями внутреннего цикла от j=i+1 до j=n-1, т.е. от индекса 1 до 3. Итак, на первой итерации внешнего цикла мы будем проверять следующую пару элементов: (7,2) (7,13) и (7,11). Теперь мы увеличиваем индекс i внешнего цикла на 1 и сверяем его с индексами от 2 до 3 (от i+1 до n-1) внутреннего цикла. Мы повторяем это до тех пор, пока не вернем правильный результат.
Примечание: здесь указан размер массива.
JavaScript
function twoSum(nums, target) {
const n = nums.length;
for (let i = 0; i < n - 1; i++) {
for (let j = i + 1; j < n; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
Python3:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n - 1):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
В худшем случае сложность времени выполнения этого алгоритма равна O(n²). Худший случай может возникнуть, когда требуемая комбинация является последней комбинацией, проверяемой нашими циклами.
Анализ сложности
- Временная сложность: O(n²)
- Космическая сложность: O(1)
Решение 2. Использование Hashmap
Эту задачу можно решить за линейное время. Идея состоит в том, чтобы использовать хеш-карту (объект в JavaScript) для хранения индексов уже видимых элементов. «Ключ» хэш-карты — это число в данном входном массиве (вы добавляете его в хэш-карту при посещении каждого элемента). «Значение» хэш-карты — это индекс числа в массиве, представленном ключом хэш-карты.
- Создайте хэш-карту, которая принимает целочисленный тип данных в качестве ключа и значения.
- Перебрать каждый элемент данного массива, начиная с первого элемента.
- На каждой итерации проверяйте, присутствует ли необходимое число (требуемое число = целевая сумма — текущее число) в хэш-карте.
- Если присутствует, верните в качестве результата [требуемый индекс номера, текущий индекс номера].
- В противном случае добавьте текущий номер итерации в качестве ключа и его индекс в качестве значения в хэш-карту. Повторяйте это, пока не найдете результат
Моделирование
Предположим, вам предоставлен входной массив ниже и цель = 24.
Пусть currIdx будет переменной, представляющей текущий обрабатываемый элемент, а idxMap будет нашей картой индекса. Ячейки, отмеченные оранжевым цветом, обозначают обрабатываемый в данный момент элемент массива.
Вначале currIdx=0 и idxMap пусто, как показано на первом рисунке ниже. Далее мы проверяем, присутствует ли требуемое число = цель — текущее число в idxMap.
Требуемое число = 24–7 = 17 отсутствует в нашей хэш-карте, поэтому мы добавляем 7 в качестве ключа idxMap и 0 в качестве значения idxMap (0 — это индекс 7 в входной массив), как показано на рисунке 2 ниже.
Далее мы переходим ко второму элементу массива, увеличивая текущий индекс. Итак, currIdx=1 указывает на элемент 2 в массиве. Снова проверяем, присутствует ли нужное число в idxMap, нужного числа = 24–2 = 22 нет в нашем хеш-мапе, поэтому добавляем в хэш-карту 2 вместе с его индексом 1.
Увеличить текущий индекс currIdx=2, который является элементом 13 во входном массиве. Опять требуемое число = 24–13 = 11 отсутствует в нашей хэш-карте. Добавьте {13:2} в idxMap. То же самое показано на схеме ниже.
Наша хеш-карта теперь содержит 3 элемента 7, 2 и 13 вместе с их индексами. Снова мы увеличиваем currIdx, currIdx=3, что соответствует элементу 11.
Теперь требуемое число = 24–11 = 13 присутствует в idxMap (показано ячейкой, выделенной зеленым на втором рисунке ниже). Это означает, что мы нашли пару, сумма которой равна целевой сумме 24, то есть (11, 13). Поэтому в качестве результата мы возвращаем индексы 11 и 13. Индекс 11 — это не что иное, как currIdx, который равен 3, а индекс 13 можно найти из нашей хеш-карты, которая равна 2, поэтому в качестве результата мы возвращаем (3, 2) или (2, 3).
JavaScript:
function twoSum(nums, target) {
const indexMap = new Map();
for (let currIndex = 0; currIndex < nums.length; currIndex++) {
const currNum = nums[currIndex];
if (indexMap.has(target - currNum)) {
return [indexMap.get(target - currNum), currIndex];
}
indexMap.set(currNum, currIndex);
}
return [];
}
Python3:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, value in enumerate(nums):
remaining = target - nums[i]
if remaining in seen:
return [i, seen[remaining]]
seen[value] = i
Анализ сложности
Временная сложность: O(n)
Пространственная сложность: O(n)
Сложность времени выполнения этого решения равна O(n), поскольку в худшем случае нам придется пройти через все элементы массива. Как описано в решении 1 с двумя суммами, худший случай возникает, когда требуемая комбинация является последней комбинацией, которую нужно проверить.
Кроме того, требуемое вспомогательное пространство равно O(n), поскольку мы храним элементы массива в хэш-карте, а в худшем случае нам придется хранить все значения в данном массиве в хэш-карте.
Это все, что касается этой статьи, спасибо, что нашли время, чтобы прочитать это. Если у вас есть какие-либо вопросы, дайте мне знать в разделе комментариев ниже, я буду более чем рад ответить.
