昆明做网站方案,网络公关公司排名,东莞家居网站建设,app软件开发的费用和流程[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和 文章目录 [双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和查找总价格为目标值的两个商品题目分析解题思路代码实现总结 三数之和题目分析解题思路代码实现总结 …[双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和 文章目录 [双指针] (三) LeetCode LCR 179. 查找总价格为目标值的两个商品 和 15. 三数之和查找总价格为目标值的两个商品题目分析解题思路代码实现总结 三数之和题目分析解题思路代码实现总结 查找总价格为目标值的两个商品
LCR 179. 查找总价格为目标值的两个商品 题目分析
(1) 数组内数字是升序
(2) 目标值为target
(3) 找两数之和为target
解题思路
找两个数字的和与目标值相等我们可以想到使用双指针解法。
解法双指针
数组是升序。
如果两个指针都在前当和小于目标值时候就无法判断移动哪个指针了。所以我们的指针是一前一后左指针从0开始右指针从size-1开始。
如果和小于目标值就让小的数字向右移动。
如果大于目标值就让大的数字向左移动。
示例 看到这里大家先去实现代码再来看后面的内容。 代码实现
class Solution {
public:vectorint twoSum(vectorint price, int target) {vectorint 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:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;sort(nums.begin(), nums.end());for(int i 0; i nums.size(); ){if(nums[i] 0) break;int left i1, 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]});//C11left, right--;while(left right nums[left-1] nums[left]) left;while(left right nums[right1] nums[right]) right--;}}i;while(i nums.size() nums[i] nums[i-1]) i;}return ret;}
};总结
细节1题目让我们去三数和为0我们把0-k当作目标值转换为两数之和。
细节2去重先对指针进行移动再进行判断“三个指针”都需要进行去重前提是保证指针不越界。
细节3left指针从k之后开始
细节4如果nums[k]到了大于0的位置我们可以提前结束循环因为没有两个正数和是负数。(例如nums[k] 1, target 0 -1 -1由于我们先进行过排序后面的都是正数。)
