题目描述

输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。

//方法：左右夹逼法,只需要2个指针,两头的数肯定乘积最小，中间的数乘积最大 。时间复杂度 O(N)，空间复杂度 O(1)
 
/*
    1.left开头，right指向结尾
    2.如果和小于sum，说明太小了，left右移寻找更大的数
    3.如果和大于sum，说明太大了，right左移寻找更小的数
    4.和相等，把left和right的数返回
*/

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left=0;
        int right=array.size()-1;
        vector<int> result;
        while(left<right)
        {
            if((array[left]+array[right])<sum)
            {
                left++;
            }
            else if((array[left]+array[right])>sum)
            {
                right--;
            }
            else
            {
                result.push_back(array[left]);
                result.push_back(array[right]);
                break;
            }
        }

        return result;
    }
};