【算法专题突破】双指针 - 和为s的两个数字（6）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法专题突破】双指针 - 和为s的两个数字（6）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. 题目解析

2. 算法原理

3. 代码编写

写在最后：

1. 题目解析

题目链接：剑指 Offer 57. 和为s的两个数字 - 力扣（Leetcode）

【算法专题突破】双指针 - 和为s的两个数字（6）,算法专题训练,c++,算法

这道题题目就一句话但是也是有信息可以提取的，

最重要的就是开始的那句话，“递增序列”

然后在数组中找出两个和为s的数即可（而且是任意一对即可）

2. 算法原理

这道题很简单，如果用暴力枚举直接两层for循环搞定就行，

但是使用暴力解法的话，就没有利用到他是有序序列的这个特性了。

看到有序一般我们会想到用二分法，但是二分比较难写，

所以我就打算利用单调性使用双指针来解这道题：

我们用 left 指针指向左边，right 指针指向右边，然后开始操作：

sum 是 left + right 的值，

如果：sum < target ，就让 left 指针右移找更大的数

如果：sum > target ，就让 right 指针左移找更小的数

如果：sum == target ，返回结果即可。

3. 代码编写

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        vector<int> ans;
        while(left < right) {
            int sum = nums[left] + nums[right];
            if(sum < target) left++;
            else if(sum > target) right--;
            else {
                ans.push_back(nums[left]);
                ans.push_back(nums[right]);
                break;
            }
        }
        return ans;
    }
};