目录
1. 题目解析
2. 算法原理
3. 代码编写
写在最后:
1. 题目解析
题目链接:剑指 Offer 57. 和为s的两个数字 - 力扣(Leetcode)
这道题题目就一句话但是也是有信息可以提取的,
最重要的就是开始的那句话,“递增序列”
然后在数组中找出两个和为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;}
};
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~