Задача
JavaScript testУсловие задачи: Напишите функцию twoSum. Она должна принимать отсортированный массив чисел arr и число k. Вернуть нужно массив из двух любых элементов, которые в сумме дают k. Если таких элементов нет, то нужно вернуть пустой массив.
Ответ:
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.