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

和为 s 的两个数字

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

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

题目解释

这道题是在数组中寻找两个元素,我们让他们的和恰好等于目标值就可以了.

算法原理

注意,这里我们寻找的是元素,不是什么下标.所以我们可以排序.这里是一道典型的双指针,还是碰撞类型的

• num[left] + num[right] < target left++
• num[left] + num[right] == target 拿到结果
• num[left] + num[right] > target right–

代码编写

class Solution
{
public:
  vector<int> twoSum(vector<int> &price, int target)
  {
    vector<int> result(2);
    sort(price.begin(), price.end());
    int left = 0;
    int right = price.size() - 1;
    while (left < right)
    {
      int sum = price[left] + price[right];
      if (target == sum)
      {
        result[0] = price[left];
        result[1] = price[right];
        return result;
      }
      else if (sum < target)
      {
        left++;
      }
      else
      {
        right--;
      }
    }
    return result;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30