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]