LeetCode — Две суммы II — входной массив отсортирован


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

Имея 1-индексированный массив целых чисел, который уже отсортирован в неубывающем порядке, найдите два числа так, чтобы их сумма равнялась определенному заданному числу. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.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.

Решение на C++

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 {};
    }
};
Вход в полноэкранный режим Выход из полноэкранного режима

Решение на Golang

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].
Вход в полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий