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:
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
同样是求数组两数之和,所以 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 {};
}
};
使用 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);
}
}