Two Sum

https://leetcode.com/problems/two-sumEasy

Условие

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

Примеры

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]

Explanation: Поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1].
Input: nums = [3, 2, 4], target = 6

Output: [1, 2]
Input: nums = [3, 3], target = 6

Output: [0, 1]

Решение

fun twoSum(nums: IntArray, target: Int): IntArray {
    // Создаем хэшмапу для хранения чисел и их индексов.
    // Ключом является число, а значением — его индекс.
    val numToIndex = mutableMapOf<Int, Int>()

    // Итерируемся по каждому элементу массива nums.
    nums.forEachIndexed { index, num ->
		    // Предполагаем, что в мапу уже добавлено первое число (n). Узнаем второе число (9 - n).
        val complement = target - num

        // Проверяем, если в мапе есть значение, равное complement
        if (numToIndex.containsKey(complement)) {
            // Возвращаем индексы найденных чисел в массиве numToIndex
            return intArrayOf(numToIndex[complement]!!, index)
        }

        // Добавляем текущее число и его индекс в мапу
        numToIndex[num] = index
    }

    // Возвращаем пустой массив, чтобы функция не ругалась (в задаче гарантировано, что решение всегда есть)
    return intArrayOf()
}

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

O(n), где n — количество элементов в массиве. Мы проходим массив только один раз, а операции вставки и поиска в мапе выполняются за O(1) в среднем.

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

O(n), так как в худшем случае все элементы массива будут добавлены в мапу.