Сумма двух чисел в отсортированном массиве

Средняя

medium , two pointers

02 September 2023

Описание задачи #

Дан массив целых чисел nums, отсортированный в возрастающем порядке. Напишите функцию twoSum для поиска в массиве двух чисел, сумма которых равна целевому числу target. В качестве результата функция должна возвращать массив с индексами элементов удовлетворяющих условию. Отсчет индексов начинается с единицы.

Ограничения #

В массиве может быть от 2 до 3 * 10⁴ уникальных значений
В качестве значений могут быть числа в диапазоне от -1000 до 1000
Массив отсортирован в возрастающем порядке
Значение target может быть в диапазоне от -1000 до 1000
Для массива всегда есть только одно решение

Примеры #

Входные данные
```
nums = [2, 5, 7, 15]
target = 9
```
Ответ: [1, 3]

Сумма 2 и 7 равна 9. Следовательно, index1 = 1, index2 = 3.
Возвращаем [1, 3].
Входные данные
```
nums = [-1, 0]
target = -1
```
Ответ: [1, 2]]

Сумма -1 и 0 равна -1. Следовательно, index1 = 1, index2 = 2.
Возвращаем [1, 2].

Решение #

Решение этой задачи сильно упрощается дополнительными условиями:

массив отсортирован в возрастающем порядке;
в массиве нет повторяющихся значений.

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

Заводим два указателя, которые будут хранить индексы. Значение left делаем равным 0, значение right равным индексу последнего элемента.
Запускаем цикл, который прервется, если left станет больше или равен right, то есть когда индексы сойдутся.
На каждой итерации высчитываем сумму элементов под индексами left и right и проверяем ее на равенство с target.

Если сумма равна target, значит мы нашли искомые числа. В таком случае возвращаем в ответе их индексы, добавив к ним единицу.
Если сумма больше target, значит мы сложили слишком большие числа и нам надо взять более маленькие. Уменьшить сумму мы можем взяв число, которое стоит левее от текущего под индексом right. Так как массив отсортирован в возрастающем порядке и в нем нет дубликатов, мы точно знаем, что число левее right будет гарантировано меньше. Уменьшаем right на 1.
Если сумма меньше target, значит мы сложили слишком маленькие числа и нам надо взять более большие. Увеличить сумму мы можем взяв число, которое стоит правее от текущего под индексом left. Так как массив отсортирован в возрастающем порядке и в нем нет дубликатов, мы точно знаем, что число правее left будет гарантировано больше. Увеличиваем left на 1.

Таким образом мы перебираем все возможные комбинации и находим конечный ответ.

package main

func twoSum(nums []int, target int) []int {
	// Устанавливаем левый указатель в нулевой индекс
	left := 0

	// Устанавливаем правый указатель в индекс последнего элемента в слайсе
	right := len(nums) - 1

	// Запускаем цикл, который прервется, если `left` и `right` сойдутся
	for left < right {
		sum := nums[left] + nums[right]

		if sum == target {
			return []int{left + 1, right + 1}
		} else if sum > target {
			right--
		} else {
			left++
		}
	}

	// Если ничего не нашли возвращаем [-1, -1]
	return []int{-1, -1}
}

export const twoSum = (nums: number[], target: number): number[] => {
    // Устанавливаем левый указатель в нулевой индекс
    let left = 0

    // Устанавливаем правый указатель в индекс последнего элемента в массиве
    let right = nums.length - 1

    // Запускаем цикл, который прервется, если `left` и `right` сойдутся
    while (left < right) {
        const sum = nums[left] + nums[right]

        if (sum === target) {
            return [left + 1, right + 1]
        } else if (sum > target) {
            right--
        } else {
            left++
        }
    }

    // Если ничего не нашли возвращаем [-1, -1]
    return [-1, -1]
}

Оценка сложности #

n - количество элементов в массиве.

По времени

Сложность по времени O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность по памяти O(1), так как мы используем только три переменных для хранения индексов и суммы.

Оригинал задачи на Leetcode

Algorithmics