Сложность: 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, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.
😎 Решение:
public class Solution {
public int[] TwoSum(int[] numbers, int target) {
int low = 0;
int high = numbers.Length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[] { low + 1, high + 1 };
} else if (sum < target) {
++low;
} else {
--high;
}
}
return new int[] { -1, -1 };
}
}Ставь 👍 и забирай 📚 Базу знаний