coding ability 展开第二幕（双指针——巩固篇）超详细！！！！

前言

本专栏的上篇，讲述了双指针的一些基础的算法习题 今天我们来学习更进一步的双指针用法吧 其实也是大相径庭，和前面的差不多，只不过题目难了一些 fellow me

有效的三角形个数

思路

第一种解法就是——暴力求解（会超时） 三层 for 循环枚举出所有的三元组，并且判断是否能构成三角形。 虽然说是暴力求解，但是还是想优化一下： 判断三角形的优化： 如果能构成三角形，需要满足**任意两边之和要大于第三边** 。但是实际上只需让**较小的两条边之和大于第三边** 即可。 因此我们可以先将原数组排序，然后从**小到大枚举三元组** ，一方面**省去枚举的数量** ，**另一方面方便判断是否能构成三角形。** 第二种解法就是——双指针 根据「解法一」中的优化思想，我们可以固定一个「最长边」，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用**「对撞指针」**来优化。 先给数组排序，然后从右边开始**指定一个数**，再在这个数的左边区间定义 **left 和 right 指针进行对撞** 如果 **nums[left] + nums[right] > nums[i]** ：**说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[i] 大的二元组** 满足条件的有 **right - left** 种 此时 right 位置的元素的所有情况相当于全部考虑完毕， right– ，进入下一轮判断 如果 **nums[left] + nums[right] <= nums[i]** ： 说明 **left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组 left 位置的元素可以舍去， left++ 进入下轮循环** 话不多说上代码吧 class Solution { public: int triangleNumber(vector& nums) { sort(nums.begin(),nums.end()); int ret = 0, n = nums.size(); for(int i = n - 1; i >= 2; i–) { int left = 0, right = i - 1; while(left < right) { if(nums[left] + nums[right] > nums[i]) { ret += right - left; right–; } else { left++; } } } return ret; } };

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

[查找总价格为目标值的两个商品]( lcof/)

思路

解法一肯定还是暴力解法，但是超时是不可避免的 就是两层for循环遍历就好啦 解法二我们使用双指针 初始化 left ， right 分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下标） 当 left < right 的时候，一直循环 当 **nums[left] + nums[right] == target** 时，说明找到结果，**记录结果，并且返回** ； 当 **nums[left] + nums[right] < target** 时： **对于 nums[left] 而言，此时 nums[right] 相当于是 nums[left] 能碰到的最大值（别忘了，这里是升序数组哈~）。如果此时不符合要求，说明在这个数组里面，没有别的数符合 nums[left] 的要求了（最大的数都满足不了你，你已经没救了）** 。 因此，我们可以**大胆舍去这个数，让 left++** ，去比较下一组数据； 那对于 nums[right] 而言，由于此时两数之和是小于目标值的， **nums[right]还可以选择比 nums[left] 大的值继续努力达到目标值，因此 right 指针我们按兵不动；** 当 nums[left] + nums[right] > target 时，同理我们可以舍去nums[right] （最小的数都满足不了你，你也没救了）。让 right– ，继续比较下一组数据，而 left 指针不变（因为他还是可以去匹配比 nums[right] 更小的数的） 其实和上一题差不多，相对来说比较简单 话不多说，上代码 class Solution { public: vector twoSum(vector& price, int target) { int left = 0, right = price.size()-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}; } };

两数之和

思路

其实和上一题差不多的，就是初始化 left 和 right 两个指针 然后对撞找出 numbers[left] + numbers[right] == target 的两个数就好啦 话不多说，上代码 class Solution { public: vector twoSum(vector& numbers, int target) { int left = 0, right = numbers.size() - 1; while(left < right) { if(numbers[left] + numbers[right] > target) { right–; } else if(numbers[left] + numbers[right] < target) { left++; } else { return {left + 1, right + 1}; } } return {-1, -1}; } };

三数之和

思路

本题与两数之和类似，与两数之和稍微不同的是，题目中要求找到所有「不重复」的三元组。 那我们可以利用在两数之和（上一题）那里用的双指针思想，来对我们的暴力枚举做优化： 先排序； 然后固定一个数 a ： 在这个数后面的区间内，使用「双指针算法」快速找到两个数之和等于 -a 即可。但是要注意的是，这道题里面需要有**「去重」操作**~ 找到一个结果之后， **left 和 right 指针要「跳过重复」的元素** ； 当使用完一次双指针算法之后，固定的 **a 也要「跳过重复」**的元素。 思路比较简单，但是代码还是有点多 class Solution { public: vector> threeSum(vector& nums) { vector> ret; int n = nums.size(); sort(nums.begin(),nums.end()); for(int i = 0; i < n; ) { if(nums[i] > 0) break; int left = i + 1, right = n - 1, target = -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]}); left++,right–; while(left < right && nums[left - 1] == nums[left]) left++;// 去重 while(left < right && nums[right + 1] == nums[left]) right–; // 去重 } } i++; while(i < n && nums[i] == nums[i - 1]) i++;// 去重处理 } return ret; } };

四数之和

思路

和上题差不多的，就是加了一个数而已啦 依次固定一个数 a ； 在这个数 a 的后面区间上，利用「三数之和」找到三个数，使这三个数的和等于 target- a 即可 class Solution { public: vector> fourSum(vector& nums, int target) { int n = nums.size(); vector> ret; sort(nums.begin(), nums.end()); for(int i = 0; i < n; ) { for(int j = i + 1; j < n; ) { int left = j + 1, right = n - 1; long long aim = (long long)target - nums[i] - nums[j]; while(left < right) { int sum = nums[left] + nums[right]; if(sum < aim) left++; else if(sum > aim)right–; else { ret.push_back({nums[i], nums[j], nums[left], nums[right]}); left++, right–; while(left < right && nums[left - 1] == nums[left]) left++; while(left < right && nums[right + 1] == nums[right]) right–; } } j++; while(j < n && nums[j] == nums[j - 1]) j++; } i++; while(i < n && nums[i] == nums[i - 1])i++; } return ret; } };

总结

今天对双指针有了新的理解，每一题的练习都是堆知识更加一步的理解 小编将持续不断为大家更新算法题，以及算法知识 一起加油呀~~~~~