OJ题：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）
一、 查找总价格为目标值的两个商品（俩数之和）
1.题目描述
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
2.示例
示例 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]
3.解题思路
1.看到这道题之后根据之前学习的相关经验，首先想到的应该是双指针的方法。
2.定义俩个指针，分别是左指针（left)、右指针(right)。让这俩个指针相加得到一个和（sum），将数组进行排序后得到一个有序数组（便于简化求和以及减少复杂度）。
a. 初始化 left ， right 分别指向数组的左右两端（这⾥不是我们理解的指针，⽽是数组的下 标） b. 当 left < right 的时候，⼀直循环 i. 当 nums[left] + nums[right] == target 时，说明找到结果，记录结果，并且返回； ii. 当 nums[left] + nums[right] < target 时： • 对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的最⼤值（别忘了，这⾥是升序数组哈~）。如果此时不符合要求，说明在这个数组里面， 没有别的数符合 nums[left] 的要求了（最⼤的数都满⾜不了你，你已经没救了）。 因此，我们可以⼤胆舍去这个数，让 left++ ，去比较下⼀组数据； • 那对于 nums[right] 而言，由于此时两数之和是⼩于目标值的， nums[right]还可以选择⽐ nums[left] ⼤的值继续努⼒达到目标值，因此 right 指针我们兵不动； iii. 当 nums[left] + nums[right] > target 时，同理我们可以舍去nums[right] （最小的数都满足不了你，你也没救了）。让 right-- ，继续⽐较下⼀ 组数据，而left 指针不变（因为他还是可以去匹配⽐ nums[right] 更⼩的数的）。 3.注意： a.返回一组数据应该使用return {price[left] , price[right]};当找到两个数的和等于目标值
target时，这行代码将执行。它创建了一个包含两个整数的vector<int>（即 C++ 中的动态数组），这两个整数分别是price数组中索引为left和right的元素。然后这个vector<int>作为函数的结果返回给调用者。这里假定你想要返回的是实际的数值，而不是它们的索引。
b.在力扣上需要返回空值时
return {-1 , -1};
这行代码会在循环结束而没有找到满足条件的两个数的情况下执行。它返回一个包含两个
-1的vector<int>，这通常用来表示未找到解或错误状态。在实际应用中，这样的返回值可以通知调用者，表明没有找到任何一对数字之和等于target。
4.代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int n = price.size();
int left = 0;
int right = n - 1;
while(left < right)
{
int sum = price[left] + price[right];
if(sum == target)
{
return {price[left] , price[right]};
}
else if(sum > target)
{
right--;
}
else
{
left++;
}
}
return {-1 , -1};
}
};二、三数之和
1.题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
2.示例
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
3.解题思路
1.面对这样一道判断三数之和的题，在数组中，我们应该首先想到固定一个值然后使用双指针的方法进行遍历解决，然后再优化代码。
2.这道题我们先将数组nums排序，然后固定一个值a，再利用双指针的方法，对固定的值的后面的数字快速找到和为-a
3.注意： 这道题需要去重操作
（1）找到一个结果之后，left和right指针要跳过重复的元素
（2）使用完一次双指针的算法之后，要跳过固定的数a
4.代码实现
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
//排序
sort(nums.begin() , nums.end());
int n = nums.size();
for(int a = 0; a < n;)
{
if(nums[a] > 0) break;
int left = a + 1, right = n - 1,target = -nums[a];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else
{
ret.push_back({nums[a] , nums[left] , nums[right]});
left++, right--;
//去重,跳过左右指针数字
while(left < right && nums[left] == nums[left - 1]) left++;
while(left < right && nums[right] == nums[right + 1]) right--;
}
}
//去重a
a++;
while(a < n && nums[a] == nums[a - 1]) a++;
}
return ret;
}
};