[剑指offer] 和为s的两个数字(C++解法)
程序员文章站
2022-07-14 18:07:09
...
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
示例 2:
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
限制:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
C++解法
思路:借鉴另外一道题(和为s的连续正数序列 )的解题思路,利用双指针的解法,实现O(n)的时间复杂度。
首先从数组的尾部往回遍历寻找到第一个小于target的数,取其下标为right,因为比target大的数明显不是答案,所以这部分数筛选掉。取left为0,sum = nums[left] + nums[right],然后进行以下循环判断:
当sum == target,则当前left和right指向的数据及为答案;
当sum < target, 则++left,增大sum的值;
当sum > target, 则–right,减小sum的值;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size() - 1, sum = 0;
while (nums[length] >= target)
--length;
int left = 0, right = length;
vector<int> vec;
while (left < right) {
sum = nums[left] + nums[right];
if (sum == target) {
vec.push_back(nums[left]);
vec.push_back(nums[right]);
return vec;
}
else if (sum < target) {
++left;
}
else
--right;
}
return vec;
}
};
上一篇: Android Studio高级控件(自动提示文本框)
下一篇: 二叉树的深度最小的