C++ 优先算法 —— 查找总价格为目标值的两个商品（双指针）
目录
题目 ：查找总价格为目标值的两个商品
1. 题目解析
2. 算法原理
Ⅰ 暴力枚举
Ⅱ 双指针算法
3. 代码实现
暴力枚举
双指针算法
题目 ：查找总价格为目标值的两个商品
1. 题目解析
题目截图：
这道题的一个关键的地方，它先说明了这是一个升序的数组，对于后面要解释的双指针的算法是重要的。
2. 算法原理
这道题有两种解法：
Ⅰ 暴力枚举
先固定一个数，然后找第二个数与它匹配，但是这个会超时，图示将在后面展示。
//伪代码演示
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
检查price[i]+price[j]的值是否等于target 这样来看，这个时间复杂度是O（N²）。
Ⅱ 双指针算法
利用单调性，使用双指针算法解决问题。
sum对应会有三种情况：
- sum>t
- sum<t
- sum==t
我们可以利用单调性来减少判断次数 ，分析如下：
所以上述left固定2，right向内枚举的情况可以直接不用考虑了，直接让left向后移动一位（left++）
接下来，继续判断sum的情况
移动后继续判断：
所以上述right固定21，left向内枚举的情况可以直接不用考虑了，直接让right向前移动一位，（right--）。
移动后再判断：
所以：
- sum>t ----> right--即可
- sum<t ----> left++即可
- sum==t ----> 返回结果
总结：利用数组有序性，然后通过一次判断就可以干掉一个数，对比暴力解法，我们需要很多次判断才能干掉一个数，但是这里利用单调性，仅需判断一次就干掉一个数，这个算法的时间复杂度是O（N）（两个指针相向遍历数组）。
3. 代码实现
题目链接：查找总价格为目标值的两个商品
暴力枚举
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int i = 0, j = 0;
int n = price.size();
for (i = 0; i < n; i++) {
for (j = i + 1; j < n; j++) {
int sum = price[i] + price[j];
if (sum == target)
return {price[i], price[j]};
}
}
return {-1, -1};
}
};提交记录：
数据少的话还是可以的：
双指针算法
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0;
int right = price.size() - 1;
while (left < right) {
if (price[left] + price[right] < target) {
++left;
} else if (price[left] + price[right] > target) {
--right;
} else {
return {price[left], price[right]};
}
}
//C++11的列表初始化，会隐式类型转化成vector
return {-1, -1};
}
};提交记录：
制作不易,若有不足之处或出问题的地方，请各位大佬多多指教 ，感谢大家的阅读支持！！!
