❄️ Продолжим разбираться в алгоритмах!
Хочу разобрать самую первую задачу на leetCode.

1. Two Sum
Описание:
Дан массив целых чисел nums и целое число target.
Нужно найти два разных индекса i и j, такие что:
nums[i] + nums[j] === target.
Вернуть нужно массив [i, j].
Гарантируется, что решение всегда есть, и один элемент нельзя использовать дважды.

❕ Решать данную задачу рекомендуется с помощью хэш-таблиц.
Хэш-таблицы - Структура данных, реализована ассоциативным массивом. Структура связывает ключи со значением.

Алгоритм работы:

Сначала заполняем хэш-таблицу: кладём туда все элементы из массива, где:
- ключ — это само число
- значение — его индекс

Затем проходим по массиву снова:
1. Для каждого числа nums[i] считаем, какое число нужно к нему в пару, чтобы в сумме получился target.
target - nums[i]
2. Проверяем: а есть ли такое число в нашей хэш-таблице?
3. Если есть, и его индекс не совпадает с текущим — возвращаем пару индексов.

Код

var twoSum = function(nums, target) {
    const hash = {};
    nums.forEach((item, index) => hash[item] = index);

    for (let i = 0; i < nums.length; i++)
    {
        let findKey = target - nums[i];

        if (hash[findKey] && hash[findKey] != i)
            return [i, hash[findKey]];
    }

    return [];
};

❄️ Задачи для практики:
217. Contains Duplicate
219. Contains Duplicate II
560. Subarray Sum Equals K

#JavaScript #Алгоритмы