输入一个递增排序的数组和一个数字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来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
下面这种做法在数据量较小的情况下是可行的，但是其复杂度达到了O(N^2)，在面对大量的数据集的情况下就会崩溃。
就是先查找一个比目标值小的数，然后遍历这个数的后面有没有正好和它相加等于目标值的数。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>target)
{
continue;
}
else
{
int tmp=target-nums[i];
for(int j=i+1;j<nums.size();j++)
{
if(nums[j]==tmp)
{
result.push_back(tmp);
result.push_back(nums[i]);
return result;
}
}
}
}
return result;
}
};
我们可以采用下面这种进阶的方法，就是先遍历一遍我们的数据，将其数据本身和数量构建一个map映射，然后再次遍历这些数据，每遍历到一个数据，就从map映射中查看时候有target减去当前值的数据存在。
这种方法将我们的时间复杂度优化到了O(2*N)，虽然能够通过leetcode的测试了，但是效率还是很低，内存开销也非常大。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
map<int,int> record;
for(auto &num:nums)
{
record[num]++;
}
for(auto &num:nums)
{
if(num>=target)
{
continue;
}
if(record[target-num])
{
result.push_back(num);
result.push_back(target-num);
return result;
}
}
return result;
}
};
这里我们注意到我们的数据是从小到大排列的，并且这组数据中一定会有一组数据是满足相加等于target的条件的，我们采用双指针法就会效率高很多。
其思路就是首相让我们的left指针指向0号元素，right指针指向我们最后一个元素，然后将我们left和right指向的数据的数值相加，得到我们的sum值，如果我们的sum值大于了target，我们就将我们的right--，也就是将我们的整体数据和减小。如果sum<target的话，我们就将我们的left++，将我们的整体数据和增大。
这样我们就能将我们的时间复杂度降到O(N)以下，极大地提升了效率。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
int left=0;
int right=nums.size()-1;
while(left<right)
{
int sum=nums[left]+nums[right];
if(sum<target)
{
left++;
}
else if(sum>target)
{
right--;
}
else
{
result.push_back(nums[left]);
result.push_back(nums[right]);
return result;
}
}
return result;
}
};