1.题目
题目分析:
在给定的数组中,找到俩个数字,且这两个数字的和与给定的target相等就行,可能会有很多组,但只要返回一组就可以。
2.算法原理
方法一:
暴力枚举法,通过俩层循环,每个循环固定一个数字,然后遍历所有数字,就可以算出所有数字的和,再去比对。
方法二:
利用单调性,使用双指针来解决,把数组最左和最右的元素相加,然后比对,如果大的话就把最大的往左移动,这样总和就变小了,然后小的话就把最小的右移动,总值就会变大,就这样依靠单调性来微调总值的大小,直到符合要求值。
3.代码实现
用到C11的语法,列表初始化。
class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0,right=price.size()-1;while(left<right){if(price[left]+price[right]>target) right--;else if(price[left]+price[right]<target) left++;else return {price[left],price[right]};}return {-1,-1};}};