题目

LCR 179. 查找总价格为目标值的两个商品

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

• 示例 1：

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

• 示例 2：

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

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

解法1：哈希表

• 哈希表解法就类似于1. 两数之和这题的解法，也就是一边遍历一边将遍历到的数可能的解存起来，然后看看后面会不会遍历到这个数

---

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        set<int> st;
        for(auto &ele:price){
            if(st.find(ele)!=st.end()) return vector<int>{ele, target-ele};
            else st.insert(target-ele);
        }
        return vector<int>{-1, -1};
    }
};

解法2：滑动指针+数学

• 哈希表解法相对于暴力遍历两轮当然复杂度不会太高，但是这道题还有一个条件是升序数组，并没有用到
• 实际上，如果利用头尾两个指针，计算其和，当过大时就让尾指针向左移动缩小和，当和过小时就让头指针向右移动增大和，这样便免去了哈希表的哈希过程的时间
• 那么这样可能错过该有的解吗？其实不会，设想和大于目标值，也就是最小的元素+最大的元素大于目标值，此时尾指针递减，其实就是直接排除了尾部元素，因为此时已经知道了最大元素与最小元素的和都会超过目标值，所以最大元素必不可能是目标值的组成元素之一，所以可以直接排除

---

class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        int i=0, j=price.size()-1, sum;
        while(i!=j){
            sum=price[i]+price[j];
            if(sum==target) return vector<int>{price[i], price[j]};
            sum<target ? ++i : --j; 
        }
        return  vector<int>{-1, -1};
    }
};