Давайте рассмотрим 14-дневный учебный план LeetCode по взлому алгоритма.
Проблема
Дан 1-индексированный массив целых чисел numbers
, который уже отсортирован в неубывающем порядке, найдите два числа, сумма которых составляет конкретный target
номер. Пусть эти два числа будут numbers[index1]
и numbers[index2]
, где 1 <= index1 < index2 <= numbers.length
.
Возвращает индексы двух чисел, index1
и index2
, добавленных на единицу, в виде целочисленного массива [index1, index2]
длины 2.
Тесты генерируются таким образом, что существует только одно решение. Вы не можете использовать один и тот же элемент дважды.
Ваше решение должно использовать только постоянное дополнительное пространство.
Пример 1:
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].
Пример 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Пример 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Ограничения:
2 <= numbers.length <= 3 * 104
1000 <= numbers[i] <= 1000
numbers
отсортировано в неубывающем порядке.1000 <= target <= 1000
- Тесты генерируются таким образом, что существует только одно решение.
Решение
Эта проблема решается с помощью двух указателей. Они пересекают массив в поисках двух чисел, которые в сумме составляют цель.
- создать указатель left в начале массива.
- создать указатель right в конце массива.
- создать переменную result в пустой массив.
- в то время как left меньше, чем right.
- пусть leftNumber будет номером left.
- пусть rightNumber будет номером справа.
- если leftNumber и rightNumber в сумме дают target, переместите оба указателя на result и прервите.
- если leftNumber и rightNumber дают в сумме больше, чем target, переместите right назад.
- если сумма leftNumber и rightNumber в сумме меньше целевого, сдвиньте влево вперед.
- выйти из цикла while
- вернуть результат.
Код
Удачного кодирования!