LeetCode-167.TwoSumII
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] <= 1000numsis 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);
}
}