【优选算法】——双指针(下篇)！

🌈个人主页：秋风起，再归来~
🔥系列专栏：C++刷题算法总结
🔖克心守己，律己则安

1、有效三角形的个数

2、查找总价值为目标值的两个商品

3、三数之和

4、四数之和

5、完结散花

1、有效三角形的个数

题目链接https://leetcode.cn/problems/valid-triangle-number/description/

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4

解题思路：

1、暴力解法：我们可以很轻松的想到枚举所有的三条变，判断它们是否可以组成三角形，记录有效三角形的个数即可。不过n^3的时间复杂度会超出时间限制！

class Solution {
public:int triangleNumber(vector<int>& nums) {int len=nums.size(),count=0;for(int a=0;a<len-2;a++){for(int b=a+1;b<len-1;b++){for(int c=b+1;c<len;c++){if(nums[a]+nums[b]>nums[c]&&nums[a]+nums[c]>nums[b]&&nums[b]+nums[c]>nums[a]) count++;}}}return count;}
};

2、更优解法：我们先将数组排序，因为判断三个数是否可以构成三角形只需要比较较小两边之和是否大于第三边即可。

3、排序后，nums[len-1]的位置就是最大值，我们先用max固定一端，right固定在max左侧，left固定在起点。

4、判断nums[left]+nums[right]是否大于nums[max]

a、如果小于，left++

b、如果大于，count+=（right-left ），固定max和right两边后，left是right之后最小的一边。如果最小的一边加上right都大于max，那其后的边一定可以构成三角形。所以我们就没有必要进行无意义的枚举。

c、此时固定max和right的情况已近枚举完成，那我们就让right--。

class Solution {
public:int triangleNumber(vector<int>& nums) {int max=nums.size()-1,count=0;//排序sort(nums.begin(),nums.end());//固定枚举maxwhile(max>=2){//固定枚举rightint right=max-1;int left=0;while(left<right){if(nums[left]+nums[right]>nums[max]) {count+=(right-left);right--;}else left++;}max--;}return count;}
};

2、查找总价值为目标值的两个商品

题目链接https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

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

由于题目比较简单，直接上代码了！

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left=0,right=price.size()-1;while(left<right){if(price[left]+price[right]<target) left++;else if(price[left]+price[right]>target) right--;else {//走隐式类型转换return {price[left],price[right]};}}return {-1,-1};}
};

3、三数之和

题目链接https://leetcode.cn/problems/3sum/description/

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 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 。

解题思路：

1、这个题目的整体思路可以转化为两数之和==target，和上一道题目相似，不过在细节上还是有些不同。

2、排序后，我们定义target在len-1的位置，left=0，right=target-1。判断nums[left]+nums[right]==-nums[target]就可以了。

>不过，这里还涉及到去重的问题：

我们找到一个三元组后，left++，right--

a.如果left==left--，那么我们找到的下一个三元组必然和前一个相等！(因为left和target固定了)

b.同理，如果right==right+1，那么我们找到的下一个三元组必然和前一个相等！

c.再有，如果target==target+1，我们在下一个区间查找的所有情况再上一个区间都查找过了！

d.所以这三种情况我们都要跳过相同的元素来进行去重操作！

解题代码：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;sort(nums.begin(),nums.end());//排序int len=nums.size();for(int target=len-1;target>=2;){if(nums[target]<0) break;//小优化int left=0,right=target-1;while(left<right){if(nums[left]+nums[right]<-nums[target]) left++;else if(nums[left]+nums[right]>-nums[target]) right--;else {ret.push_back({nums[left++],nums[right--],nums[target]});//去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//去重target--;while(target>=2&&nums[target]==nums[target+1]) target--;}return ret;}
};

4、四数之和

题目链接https://leetcode.cn/problems/4sum/description/

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

解题思路：

1、这道题目的整体思路和三数之和差不多，我们可以把上一题理解为两数之和==target(0) - 一个数（自己固定枚举）。

2、而这道题目无非就是再三数之和的基础上，再多枚举一个数而已！

解题代码：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int len=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int d=len-1;d>=3;){if(target<0&&nums[0]>=0) break;//小优化//三数之和逻辑for(int c=d-1;c>=2;){long long tmp=(long long)target-nums[c]-nums[d];int left=0;int right=c-1;while(left<right){if(nums[left]+nums[right]<tmp) left++;else if(nums[left]+nums[right]>tmp) right--;else{ret.push_back({nums[left++],nums[right--],nums[c],nums[d]});//left,right去重while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}//c去重c--;while(c>=2&&nums[c]==nums[c+1]) c--;}//d去重d--;while(d>=3&&nums[d]==nums[d+1]) d--;}return ret;}
};