【C++】双指针算法：和为s的两个数字

1.题目

虽然在牛客上是个中等题，但我感觉是比较简单的。大家在看完这篇文章后可以看看我的上一篇文章：有效三角形的个数。本文章的题目的解法只是有效三角形的个数这道题目的一个环节。看懂这篇文章后可以更好的解决有效三角形个数那道题目！

2.算法思路

我们需要利用好数组的有序性。

可以定义left和right指针，分别从左右两边遍历数组。left对应的数计为a,right对应的数计为b,则有:

若a+b>s right--；若a+b<s left++;若a+b==s 返回。

3.提交结果与代码实现

class Solution {
public:

    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int left=0,right=array.size()-1;
        while(left<right){
            if(array[left]+array[right]<sum) left++;
            else if(array[left]+array[right]>sum) right--;
            else return {array[left],array[right]};
        }
        return {};
    }
};

时间复杂度分析：

遍历了一次数组，时间复杂度：O(n)。

空间复杂度分析：

定义了两个变量，空间复杂度：O(1)。