LeetCode-167.TwoSumII

王强

发布于 2021-01-18 21:07:48

4340

1. 描述

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

Your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.

Example 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.

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]

Constraints:

2 <= nums.length <= 3 * 104
-1000 <= nums[i] <= 1000
nums is sorted in increasing order.
-1000 <= target <= 1000

2. 分析及实现

同样是求数组两数之和，所以 LeetCode 的第一题 Two Sum 的解法在此同样适用。但是既然本题的数组已经排序好了，一定会有更有效率的解决方案。要使用的方案是 双指针 法：一个指针初始化指向最小元素，向右遍历；一个指针初始化指向最大元素，向左遍历。

如果两个指针指向元素的和为 target，则这两个数就是我们要找的。如果两个指针指向元素的和大于 target ，把右边的指针向左移一位，使得两数之和变得小一些。如果两个指针指向元素的和小于 target，把左边的指针向右移一位，使得两数之和变得大一些。直到找到和为 target 的两个元素。

下面举一个例子，有一个数组 a = [1, 4, 5, 8, 17, 19, 27, 50, 79] ，寻找和为 32 的两个元素。

定义两个指针 l = 0 和 r = 8，求得 a[0] + a[8] 和为 81 ，该值大于 32， r 向左移变成 7。

a[0] + a[7] 和为 52 ，该值大于 32， r 向左移变成 6。

a[0] + a[6] 和为 28 ，该值小于 32，l 向右移变成 1。

a[1] + a[6] 和为 31 ，该值小于 32，l 向右移变成 2。

a[2] + a[6] 和为 32 这两个元素就是我们要找的。

注意：本题返回的并不是两个元素的下标，而是两个下标分别加一，上面的例子两个元素下标分别为 {2, 6}，返回的是 {3, 7}。

代码如下：

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

            if (sum < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return {};
    }
};

3. 测试用例

使用 Catch2 进行测试，项目配置详见 github[1]。

TEST_CASE("TwoSumII", "[twoSumII]")
{
    Solution solution;

    SECTION("1")
    {
        vector<int> expected_result{1, 2};
        vector<int> nums{2, 7, 11, 15};
        vector<int> result = solution.twoSum(nums, 9);
        REQUIRE(CompareVectors<int>(expected_result, result) == true);
    }
    SECTION("2")
    {
        vector<int> expected_result{2, 4};
        vector<int> nums{2, 7, 11, 15};
        vector<int> result = solution.twoSum(nums, 22);
        REQUIRE(CompareVectors<int>(expected_result, result) == true);
    }
    SECTION("3")
    {
        vector<int> expected_result{3, 7};
        vector<int> nums{1, 4, 5, 8, 17, 19, 27, 50, 79};
        vector<int> result = solution.twoSum(nums, 32);
        REQUIRE(CompareVectors<int>(expected_result, result) == true);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-01-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 C与Python实战微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度