购物车内的商品价格按照升序记录于数组 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

可以通过hashmap来记录每个值所需的目标值，遍历一次就能找到

注意到数组是有序的，同样倒过来遍历也是有序的，可以采用双指针的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int> &price, int target) {
        int l = 0;
        int r = price.size() - 1;
        while (l <= r) {
            if (price[l] + price[r] < target) {
                l++;
            } else if (price[l] + price[r] > target) {
                r--;
            } else {
                return {price[l], price[r]};
            }
        }
        return {};
    }
};