Сумма двух чисел в массиве

Легкая

easy , array , hash table

30 August 2023

Описание задачи #

Дан массив целых чисел nums. Напишите функцию twoSum для поиска в массиве двух чисел, сумма которых равна целевому числу target. В качестве результата функция должна возвращать массив с индексами элементов удовлетворяющих условию. Порядок индексов в ответе не важен.

Ограничения #

В массиве может быть от 2 до 10⁴ уникальных значений
В качестве значений могут быть числа в диапазоне от -10⁹ до 10⁹
Значение target может быть в диапазоне от -10⁹ до 10⁹
Для массива всегда есть только одно решение

Примеры #

Входные данные
```
nums = [2, 7, 11, 15]
target = 9
```
Ответ: [0, 1] или [1, 0]

Сумма 2 и 7 равна 9. Следовательно, index1 = 0, index2 = 1.
Возвращаем [0, 1].
Входные данные
```
nums = [-1, 0]
target = -1
```
Ответ: [0, 1] или [1, 0]

Сумма -1 и 0 равна -1. Следовательно, index1 = 0, index2 = 1.
Возвращаем [0, 1].

Решение #

Для того чтобы эффективно решить эту задачу, надо придумать, как получать индекс числа из массива не перебирая его. В этом нам может помочь структура Hash Map (или ее аналоги), которая позволяет получать значение по ключу за константное время.

Изначально мы инициализируем пустую мапу, в которую будем записывать в качестве ключа число, а в качестве значения — его индекс в массиве. Далее запускаем цикл по всем элементам массива, в котором выполняем следующие проверки на каждой итерации.

Высчитываем разницу между target и текущим числом из массива. Это второе искомое число, которое нам нужно.
Чтобы проверить, есть ли число в массиве, мы обращаемся в нашу мапу с текущим числом в качестве ключа. Если в мапе есть такое число, значит мы его уже ранее добавляли из массива и можем получить его индекс. Мы нашли искомую пару чисел и можем вернуть их индексы в виде массива в качестве ответа.
Если в мапе нет такого числа, значит нужно его туда добавить. В качестве ключа используем само число, а в качестве значения его индекс.

package main

func twoSum(nums []int, target int) []int {
	// Создаем мапу для отслеживания индексом чисел из слайса.
	indexMap := make(map[int]int)

	for i, num := range nums {
		// Рассчитываем второе искомое число
		complement := target - num

		// Проверяем, есть ли индекс для этого числа в мапе
		secondIndex, ok := indexMap[complement]

		// Если индекс для числа уже есть в мапе, значит мы нашли искомую пару
		if ok {
			return []int{i, secondIndex}
		}

		// Если индекс для числа еще не добавлен, то записываем его в мапу
		indexMap[num] = i
	}

	return nil
}

export const twoSum = (nums: number[], target: number): number[] => {
    // Создаем объект для отслеживания индексом чисел из массива
    // Также можно использовать new Map(), но объект делает в точности то же самое и с ним немного проще работаь.
    const indexMap: Record<number, number> = {}

    for (let i = 0; i < nums.length; i++) {
        // Рассчитываем второе искомое число
        const complement = target - nums[i]

        // Проверяем, есть ли индекс для этого числа в объекте
        const secondIndex = indexMap[complement]

        // Если индекс для числа уже есть в объекте, значит мы нашли искомую пару
        if (secondIndex > -1) {
            return [i, secondIndex]
        }

        // Если индекс для числа еще не добавлен, то записываем его в объект
        indexMap[nums[i]] = i
    }

    return []
}

Оценка сложности #

n - количество элементов в массиве.

По времени

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

По памяти

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

Оригинал задачи на Leetcode

Algorithmics