Сложность: medium
Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length.
Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2].
Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды.
Ваше решение должно использовать только константное дополнительное пространство.
Пример:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
👨💻 Алгоритм:
1️⃣Инициализация указателей:
Используйте два указателя: один (left) начинается с начала массива, а другой (right) - с конца.
2️⃣Поиск решения:
Сравните сумму элементов, на которые указывают left и right, с целевым значением target.
Если сумма равна target, верните индексы этих элементов как решение.
Если сумма меньше target, увеличьте left (так как массив отсортирован и увеличение left увеличивает сумму).
Если сумма больше target, уменьшите right (чтобы уменьшить сумму).
3️⃣Продолжение до нахождения решения:
Перемещайте указатели left и right, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.
😎 Решение:
var twoSum = function (numbers, target) {
let low = 0;
let high = numbers.length - 1;
while (low < high) {
let sum = numbers[low] + numbers[high];
if (sum == target) {
return [low + 1, high + 1];
} else if (sum < target) {
low++;
} else {
high--;
}
}
return [-1, -1];
};Ставь 👍 и забирай 📚 Базу знаний