Leetcode算法解析——查找总价格为目标值的两个商品

1. 题目链接：LCR 179. 查找总价格为目标值的两个商品

2. 题目描述：

商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]
1
2

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]
1
2

提示：

• 1 <= price.length <= 10^5
• 1 <= price[i] <= 10^6
• 1 <= target <= 2*10^6

3. 暴力枚举（超时）

3.1 算法思路

用两层循环把所有的可能性都列举出来，然后判断是否有等目标值的两个数

3.2 算法流程

1. 外层循环枚举第一个数
2. 内层循环枚举第二个数，与第一个进行匹配
3. 如果两个数相加等于目标值，返回这两个数

3.3 C++算法代码

class Solution {
public:
    vector twoSum(vector& price, int target) {
        for(int i=0;i

class Solution {
public:
    vector twoSum(vector& price, int target) {
        int n=price.size();
        //设置左右指针
        int left=0,right=n-1;
        while(lefttarget)
            right--;
            //小于左指针++
            else if(price[left]+price[right]