Давайте рассмотрим 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
  • Тесты генерируются таким образом, что существует только одно решение.

Решение

Эта проблема решается с помощью двух указателей. Они пересекают массив в поисках двух чисел, которые в сумме составляют цель.

  1. создать указатель left в начале массива.
  2. создать указатель right в конце массива.
  3. создать переменную result в пустой массив.
  4. в то время как left меньше, чем right.
  5. пусть leftNumber будет номером left.
  6. пусть rightNumber будет номером справа.
  7. если leftNumber и rightNumber в сумме дают target, переместите оба указателя на result и прервите.
  8. если leftNumber и rightNumber дают в сумме больше, чем target, переместите right назад.
  9. если сумма leftNumber и rightNumber в сумме меньше целевого, сдвиньте влево вперед.
  10. выйти из цикла while
  11. вернуть результат.

Код

Удачного кодирования!