Blind 75 — Вопросы по программированию и техническому интервью — серия объяснений

Проблема:

Дан 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. Two Sum с тем отличием, что массив отсортирован в порядке неубывания. Это позволяет выполнять более быстрый поиск, но следует использовать другой метод, чем хэш-карту или грубую силу. Использование левого и правого указателей, установленных на ноль, и длину массива минус один, а также использование цикла while лучше всего подходят для этой проблемы. Если левое плюс правое равно целевому, то мы можем вернуть эти индексы, и тогда у нас есть только один простой вопрос, который нужно задать после этого: левое плюс правое больше или меньше целевого? Если она больше, то мы, конечно, должны уменьшать правый указатель, чтобы уменьшить следующую сумму, а если меньше, то мы увеличиваем левый указатель.

Лево-правое решение — O(n)

Сначала инициализируйте левый и правый указатели. Теперь в цикле while. Мы будем повторять, пока левое меньше правого, а не меньше или равно, потому что мы не можем использовать один и тот же элемент дважды. Чтобы сделать код немного чище, мы сохраняем сумму левого и правого в переменную. Затем проверьте, равен ли он целевому, и если да, то верните индексы плюс один, потому что в задаче указано, что он имеет индекс 1, а не индекс 0. Если оно не равно, оно либо больше, либо меньше целевого значения. Если больше, уменьшите правую часть на 1, в противном случае увеличьте левую на единицу. Как указано в задаче, мы гарантированно найдем решение, поэтому нам не нужно иметь оператор возврата после цикла.

class Solution:
 def twoSum(self, numbers: List[int], target: int) -> List[int]:
  l, r = 0, len(numbers) — 1
 
  while l < r:
   tot = numbers[l] + numbers[r]
 
   if tot == target:
    return [l + 1, r + 1]
   elif tot > target:
    r -= 1
   else:
    l += 1

Информация:

Веб-сайт: nkwade.dev
LinkedIn: linkedin.com/in/nkwade
GitHub: github.com/nkwade
Электронная почта: [email protected]