Теперь рассмотрим немного усложненную версию предыдущей задачи. Хотя, я бы даже сказал, что она сильно проще.
Сложность: 🟠 Cредняя
ℹ️ Описание
Дан массив целых чисел nums, отсортированный в возрастающем порядке.
Напишите функцию twoSum которая будет находить в массиве два числа, сумма которых равна определенному целевому
числу target.
В качестве результата функция должна возвращать массив с индексами элементов, удовлетворяющих условию. Отсчет индексов начинается с единицы.
⚠️ Ограничения
🔹 В массиве может быть от 2 до 3 * 10^4 уникальных значений
🔹 В качестве значений могут быть числа в диапазоне от -1000 до 1000
🔹 Массив отсортирован в возрастающем порядке
🔹 Значение target может быть в диапазоне от -1000 до 1000
🔹 Для массива всегда есть только одно решение
1️⃣ Пример
Вход:
nums = [2, 5, 7, 15]
target = 9Ответ:
[1, 3]Сумма 2 и 7 равна 9. Следовательно,
index1 = 1, index2 = 3.Возвращаем
[1, 3].2️⃣ Пример
Вход:
nums = [-1, 0]
target = -1Ответ:
[1, 2]
Сумма -1 и 0 равна -1. Следовательно,
index1 = 1, index2 = 2.Возвращаем
[1, 2].✅ Решение
Решение этой задачи сильно упрощается дополнительными условиями:
- массив отсортирован в возрастающем порядке;
- в массиве нет повторяющихся значений.
Благодаря этим условиям задачу можно решить простым перебором при помощи двух указателей, используя следующий алгоритм.
1. Заводим два указателя, которые будут хранить индексы. Значение left делаем равным 0, значение right равным индексу последнего элемента.
2. Запускаем цикл, который прервется, если left станет больше или равен right, то есть когда индексы сойдутся.
3. На каждой итерации высчитываем сумму элементов под индексами left и right и проверяем ее на равенство с target.
- Если сумма равна target, значит мы нашли искомые числа. В таком случаем возвращаем в ответе их индексы, добавив к ним единицу.
- Если сумма больше чем target, значит мы сложили слишком большие числа и нам надо взять более маленькие. Уменьшить сумму мы можем взяв число, которое стоит левее от текущего под индексом right.
Так как массив отсортирован в возрастающем порядке и в нем нет дубликатов, мы точно знаем, что число левее right будет гарантировано меньше. Уменьшаем right на 1.
- Если сумма меньше чем target, значит мы сложили слишком маленькие числа и нам надо взять более большие. Увеличить сумму мы можем взяв число, которое стоит правее от текущего под индексом left.
Так как массив отсортирован в возрастающем порядке и в нем нет дубликатов, мы точно знаем, что число правее left будет гарантировано больше. Увеличиваем left на 1.
Таким образом мы перебираем все возможные комбинации и находим конечный ответ.
Посмотреть реализацию
🅾️ Оценка сложности
n - количество элементов в массиве
Сложность по времени O(n), так как мы итерируемся по всем элементам массива.
Сложность по памяти O(1), так как мы используем только три переменных для хранения индексов и суммы.
#medium #arrays