剑指 Offer 57. 和为s的两个数字

一、题目

输入一个递增排序的数组和一个数字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

二、题目分析&解题思路

2.1 从头往后遍历法

有没有人和我一样，想着从头往后遍历，例如 第一个用例
2，7，11，15
依次把每个数字 与 target - nums[i] 存到 map 里
存成这样：
2，7
7，2
…
例如先 存 2，7
再遍历 7 时 计算 target - 7 = 2 ,再去用 map.find(2); 找到了即可
否则继续往后遍历

代码实现：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {map<int, int> mapTemp;for(int i = 0; i < nums.size(); i++){if(nums[i] > target){break;}int iTemp = target - nums[i];if(mapTemp.find(iTemp) == mapTemp.end()){mapTemp.insert(make_pair(nums[i], iTemp));}else{nums.resize(0);auto iter = mapTemp.find(iTemp);nums.push_back(iter->first);nums.push_back(iter->second);break;}}return nums;}
};

虽然过了但是可以看到，所耗时间和所额外开辟的空间都非常大，这代码还不如不写
时间复杂度：常规遍历 O(N) 加上每一次的 map.find nLog(n) ,还额外开辟了map 存储 2N的空间，太鸡肋了，完全忽略了 升序这一个特点；
因此可以考虑使用双指针法

2.2 双指针遍历法

以示例 1 的用例来看，数组是升序，左小右大，那么只需要做如下操作：

代码实现：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left = 0;int right = nums.size() -1;while(left < right){if((nums[left] + nums[right]) > target){//说明右边的数字太大了right--;}else if((nums[left] + nums[right]) < target){//说明左边的数字太小了left++;}else{nums[0] = nums[left];nums[1] = nums[right];nums.resize(2);break;}}return nums;}
};

是不是立马好了一点，但是感觉还是很慢，还有没有优化的空间呢？

2.3 缩减范围+双指针法

我们继续来看 这一组用例
2 7 11 15
target = 9;
用双指针的话，其实 11 15 这两个数字完全没有必要去遍历，因为 其 已经 大于 target 了。且题目已经告知

说明没有负数，那么说明这一部分可以舍去，可以做一个裁剪，把范围缩小，把多余的右部分数组元素舍去，减少 双指针法的 right 区间，降低时间复杂度。

    int GetRightIndex(vector<int>& nums, int target){int left = 0;int right = nums.size()-1;while(left < right){int mid = (left + right) /2;if(nums[mid] < target){left = mid + 1;}if(nums[mid] >= target){right = mid;}}return right;}

可以看到速度有效提升

三、代码实现

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int left = 0;int right = GetRightIndex(nums, target);while(left < right){if((nums[left] + nums[right]) > target){//说明右的数字太大了right--;}else if((nums[left] + nums[right]) < target){//左边的数字太小了left++;}else{nums[0] = nums[left];nums[1] = nums[right];nums.resize(2);break;}}return nums;}int GetRightIndex(vector<int>& nums, int target){int left = 0;int right = nums.size()-1;int mid = 0;while(left < right){mid = (left + right) /2;if(nums[mid] < target){left = mid + 1;}if(nums[mid] >= target){right = mid;}}return right;}
};