Постановка задачи

Дан 1-индексированный массив целых чисел числа, который уже отсортирован в неубывающем порядке, найти два числа таким образом, чтобы в сумме они составляли определенное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 ‹= index1 ‹ index2 ‹= number.length.

Возвращает индексы двух чисел, index1 и index2, добавленные на единицу, в виде целочисленного массива [index1, index2] длины 2.

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

Ваше решение должно использовать только постоянное дополнительное пространство.

Постановка задачи взята с: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

Пример 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 * 10^4
- -1000 <= numbers[i] <= 1000
- numbers are sorted in non-decreasing order.
- -1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.

Объяснение

Бинарный поиск

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

Входной массив отсортирован, что упрощает использование концепции бинарного поиска. Давайте проверим алгоритм непосредственно.

- initialize i = 0, j = numbers.size() - 1
  sum = 0
- loop while i < j
  - sum = numbers[i] + numbers[j]
  - if sum > target
    - decrement: j--
  - else if sum < target
    - increment: i++
  - else
    // when the sum is equal to the target
    - return [i + 1, j + 1]
- while end
- return []

Давайте проверим наш алгоритм на C++, Golang и Javascript.

С++ решение

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i = 0, j = numbers.size() - 1;
        int sum;
        while(i < j) {
            sum = numbers[i] + numbers[j];
            if(sum > target) {
                j--;
            } else if(sum < target) {
                i++;
            } else {
                return { i + 1, j + 1 };
            }
        }
        return {};
    }
};

Голанг решение

func twoSum(numbers []int, target int) []int {
    i, j := 0, len(numbers) - 1
    sum := 0
    for i < j {
        sum = numbers[i] + numbers[j]
        if sum > target {
            j--
        } else if sum < target {
            i++
        } else {
            return []int{ i + 1, j + 1 }
        }
    }
    return []int{}
}

Javascript-решение

var twoSum = function(numbers, target) {
    let i = 0, j = numbers.length - 1;
    let sum = 0;
    while(i < j) {
        sum = numbers[i] + numbers[j];
        if(sum > target) {
            j--;
        } else if(sum < target) {
            i++;
        } else {
            return [i + 1, j + 1];
        }
    }
    return [];
};

Давайте протестируем наш алгоритм для примера 1.

Input: numbers = [2, 7, 11, 15]
       target = 9
Step 1: set i = 0
            j = numbers.size() - 1
              = 4 - 1
              = 3
            sum = 0
Step 2: loop while i < j
        0 < 3
        true
        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 15
            = 17
        if sum > target
           17 > 9
           true
           j--
           j = j - 1
             = 3 - 1
             = 2
Step 3: loop while i < j
        0 < 2
        true
        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 11
            = 13
        if sum > target
           13 > 9
           true
           j--
           j = j - 1
             = 2 - 1
             = 1
Step 4: loop while i < j
        0 < 1
        true
        sum = numbers[i] + numbers[j]
            = numbers[0] + numbers[3]
            = 2 + 7
            = 9
        if sum > target
           9 > 9
           false
        else if sum < target
           9 < 9
           false
        else
           return [i + 1, j + 1]
           return [0 + 1, 1 + 1]
           return [1, 2]
We return the answer as [1, 2].

Первоначально опубликовано на https://alkeshghorpade.me.

Если этот пост был полезен, пожалуйста, несколько раз нажмите кнопку аплодисментов 👏, чтобы выразить свою поддержку автору 👇

🚀Разработчики: учитесь и развивайтесь, не отставая от того, что важно, ПРИСОЕДИНЯЙТЕСЬ К FAUN.