题目解析:
这个题我们可以看成是要找出来数组中两个相加等于target
的数字。
输入一个递增排序的数组和一个数字s,也就是说数组中的数字是有序的,将数组中相加等于s的两个数字组合输出即可。
算法原理:
解法一:暴力解法
暴力枚举策略:将数组中的所有组合都枚举出来,用两层for循环,伪代码展示:for(int i=0;i<n;i++) for(int j=i+1;j<n;j++)
这样做的不好处就是时间复杂度会上升。
解法二:利用单调性,使用双指针算法解决问题
将left
放置在索引为0的位置,right
放置在n-1的位置,这里给一个详细的例子数组[ 2 7 11 15 19 21 ]
,target
为30,首先left
是指向2的位置,right
放置在21的位置,此时left+right
,sum
值小于target
,最小的数字和最大的数字相加都小于target
,那么就说明这个最小的数字跟其他数字相加也会小于target
,利用单调性的知识我们可以明白,此时就是说left
太小了,所以需要left++
,换一个更大一点的数字进行相加的对比;所以将left
指向7的位置,right
指向21,相加还是小于target
,接着让left指向11,让right
指向21,相加此时发现大于target
,也就是说此时的right
太大了,让right--
到下一个位置;此时left
等于11,right
=19,相加等于target
,符合要求,返回即可。
下面我们就将思路转换为代码写出OJ题;
这道题目最后要让我们找出数组中两个相加等于target
的数字,而且任意返回一对就好,我们用双指针算法解决这个问题,定义left=0,right=nums.size()-1;
分别找到left
和right
的初始位置,接着定义一个sum
存储相加之后的值,将sum
跟target
进行对比,
sum>target:
说明right太大了,right--
;sum<target:
说明left太小了,left++
;sum=target
:返回nums[left],nums[right]
但是由于题目中没有给出一整个数组中都找不到两个相加等于target
的数,原则上我们已经完成了题目的要求,但是提交代码的时候还会报错,所以要考虑一下编译器,最后我们任意返回两个值,假设编译器没有找到符合条件的值。return{-1,-1};
大括号里可以是任意的值。
```class Solution {
public:
vector twoSum(vector& price, int target) {
int left=0,right=price.size()-1;
while(left<right)
{
int sum=price[left]+price[right];
if(sum<target) left++;
else if(sum>target) right--;
else return {price[left],price[right]};
}
//并不是所有题目都有返回值,这里需要照顾一下编译器
return{-1,-1};
}
};
```