Функция twoSum

Ответ:

function twoSum(arr, k) {
    let l = 0,
        r = arr.length - 1;
    while (l < r) {
        const sum = arr[l] + arr[r];
        if (sum === k) {
            return [arr[l], arr[r]];
        }
        if (sum < k) {
            l++;
        } else {
            r--;
        }
    }
    return [];
}

Объяснение:

Данную задачу можно решить разными способами, здесь описан сам оптимальный (сложность алгоритма по времени равна O(n) а по памяти O(1)). Сначала заводим два указателя на первый элемент и на последний. Затем в цикле while считаем сумму элементов, на которые указывают указатели.

Если сумма равна заданному числу k, то возвращаем эти элементы. Если сумма меньше k, значит, нужно эту сумму увеличить. Для этого двигаем левый указатель вправо на 1. Ну а если сумма больше k, то сумму нужно уменьшить, для этого двигаем правый указатель влево на 1.

Код для проверки:

function twoSum(arr, k) {
    let l = 0,
        r = arr.length - 1;
    while (l < r) {
        const sum = arr[l] + arr[r];
        if (sum === k) {
            return [arr[l], arr[r]];
        }
        if (sum < k) {
            l++;
        } else {
            r--;
        }
    }
    return [];
}

console.log(twoSum([-1, 2, 5, 6], 7));
console.log(twoSum([-3, -1, 0, 2, 6], 6));
console.log(twoSum([2, 4, 5], 8));
console.log(twoSum([-9, -5, -2, -1, 1, 4, 9, 11], 3));