Печально известная проблема двух сумм. (Серия 3 DSA)

Проблема

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

• Пример
• Вход: nums = [2,7,11,15], target = 9
• Выход: [0,1]
• Объяснение: Поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1].
• Вход: nums = [3,2,4], цель = 6
• Выход: [1,2]
• Вход: nums = [3,3], цель = 6
• Выход: [0,1]

Решение

• ЭТО РЕШЕНИЕ БУДЕТ РАБОТАТЬ ТОЛЬКО В ТОМ СЛУЧАЕ, ЕСЛИ ЭЛЕМЕНТЫ ОТСОРТИРОВАНЫ
• Пусть есть два указателя, один указывает на начало массива (low), а другой — на конец массива (high).
• while low < high,
• если сумма значений в low и high = target, возвращаем индексы
• если сумма значений low и high > target, уменьшите индекс high на 1
• если сумма значений low и high < target, увеличить индекс low на 1

function twoSum(array, target){
    let low = 0;
    let high = array.length - 1;

    while (low < high) {
        const sum = array[low] + array[high];
        if (sum === target) return [low, high];
        if (sum > target) high--;
        else if (sum < target) low++;
    }
}

Метод второй

/**
 * 
 * Input: nums = [2,7,11,15], target = 9 
 * Output: [0,1]
 * Initialize a map,
 * loop through array, 
 * subtract currentItem from target to get compliment, 
 *  if compliment exist in map, return [currentItmIdx, compliment[]]
 * else add map[curentItem] = idx
 * @param {*} array 
 * @param {*} target 
 */
function twoSumMethod2(array, target){
    const map = {};

    for (let i = 0; i < array.length; i++) {
        let com = target - array[i];
        if(map[com] !== undefined) return [i, map[com]]
        else map[array[i]] = i;
    }
    return -1
}

Примеры тестов

const nums = [2,7,11,15], цель = 9;
const nums = [3,3], цель = 6

—

В любом случае, если у вас есть лучший способ решения, вы можете оставить свое решение в комментариях. Я не эксперт. Просто учусь вслух.

Не забудьте поставить лайк, поделиться и оставить комментарий. 🙂