Two Sum

Классическая задача на алгоритмы с собеседования.

Задача.

Дан массив целых чисел. Надо найти пару чисел в массиве, сумма которых равна заданному числу. В качестве результата вернуть индексы этих элементов. Можно считать, что такая пара есть всегда и только одна.
Например:
Для массива nums = [2, 11, 15, 7], target = 9
Ответ: [0,3]
Т.к. nums[0] + nums[3] = 2 + 7 = 9

Решение.

На ум сразу приходит очевидное решение: перебрать все пары чисел и проверить, что их сумма равна заданному числу.

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (i != j && nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[] {-1, -1};
}

Такое решение работает за O(n^2) по времени, т.к. у нас два вложенных цикла. Space Complexity O(1), т.к. никакой дополнительной памяти мы не используем, за исключением нескольких переменных примитивного типа.

Это решение можно улучшить до линейного при помощи hash-таблицы.
Будем в цикле идти по массиву и кэшировать все числа массива, которые мы уже видели, в этой hash-таблице.

Далее, чтобы получить заданную сумму, нам нужно чтобы
nums[i] + второе число из массива = target
Т.е. для текущего индекса i это другое число в массиве должно быть:
второе число из массива = target - nums[i].
Проверим, не встречалось ли нам уже это число раньше при проходе массива. Сделать это можно просто проверив, не хранится ли оно в нашей hash-таблице.

Назовем это второе число complementaryNumber.

Когда код решения:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        //Вычисляем значение нашего второго дополнительного числа 
        //до пары
        int complementaryNumber = target - nums[i];
        //Если мы его уже видели - мы нашли нашу пару
        if (map.containsKey(complementaryNumber)) {
            return new int[] {i, map.get(complementaryNumber)};
        }
        //кэшируем числа и их индексы, которые мы ранее видели в 
        //массиве
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

Это решение работает на O(n) (линейное время). Space Complexity при этом тоже O(n), т.к. мы еще храним значения из массива в hash-таблице, размер которой будет пропорционален размеру массива.

У этой задачи есть множество вариаций. Например, можно ли еще улучшить это решение если массив отсортирован? Или найти не индексы, а сами числа. Или найти тройки или четверки чисел, сумма, которых равна заданному значению.

Разборы этих вариаций будут в будущем на моем канале.