[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和
查找总价格为目标值的两个商品
LCR 179. 查找总价格为目标值的两个商品
题目分析
(1) 数组内数字是升序
(2) 目标值为target
(3) 找两数之和为target
解题思路
找两个数字的和与目标值相等,我们可以想到使用双指针解法。
解法:双指针
数组是升序。
如果两个指针都在前,当和小于目标值时候,就无法判断移动哪个指针了。所以我们的指针是一前一后:左指针从0开始,右指针从size-1开始。
如果和小于目标值,就让小的数字向右移动。
如果大于目标值,就让大的数字向左移动。
示例:
看到这里,大家先去实现代码,再来看后面的内容。
代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
vector<int> ret;
int left = 0, right = price.size()-1;
while(left != right)
{
if(price[left] + price[right] > target) right--;
else if(price[left] + price[right] < target) left++;
else
{
ret.push_back(price[left]);
ret.push_back(price[right]);
break;
}
}
return ret;
}
};
总结
这道题比较简单。
三数之和
15. 三数之和
题目分析
(1) 找三数之和为0
(2) 三数不可以重复
解题思路
这和之前的两数之和十分相似,我们可以把它转变成两数之和来做。(首先理解上一道题)
解法:双指针
我们可以先排序,再让target = 0 - k(k为三数中的任意一个),这样就变成了求两数之和了(left从k后面的位置,right为size-1)。
即为:排序后,我们固定一个数为k,从它后面的数中找出两个数和为0-k即可。
最后我们必须保证不能有重复的数返回:
排序后,相同的数都会相邻,在找出一组数后,我们将左右指针分别进行迭代,去重。
当然固定的k也需要去重,和上面的方法一样。
示例:nums[] = {-4, -4, -4, 0, 0, 0, 1, 3, 4, 4, 4}
看到这里,先去尝试实现代码,再来看下面的内容吧。
代码实现
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); )
{
if(nums[i] > 0) break;
int left = i+1, right = nums.size()-1;
int target = 0 - nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum > target) right--;
else if(sum < target) left++;
else
{
ret.push_back({nums[i], nums[left], nums[right]});//C++11
left++, right--;
while(left < right && nums[left-1] == nums[left]) left++;
while(left < right && nums[right+1] == nums[right]) right--;
}
}
i++;
while(i < nums.size() && nums[i] == nums[i-1]) i++;
}
return ret;
}
};
总结
细节1:题目让我们去三数和为0,我们把0-k当作目标值,转换为两数之和。
细节2:去重,先对指针进行移动,再进行判断;“三个指针”都需要进行去重;前提是保证指针不越界。
细节3:left指针从k之后开始文章来源:https://www.toymoban.com/news/detail-744012.html
细节4:如果nums[k]到了大于0的位置,我们可以提前结束循环,因为没有两个正数和是负数。(例如nums[k] = 1, target = 0 -1 = -1;由于我们先进行过排序,后面的都是正数。)文章来源地址https://www.toymoban.com/news/detail-744012.html
到了这里,关于[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!