算法：双指针系列（二）——对撞指针

双指针系列（二）——对撞指针

• （一）盛水最多的容器
• • （一）题目分析
  • （二）代码展示
• 二、有效的三角形个数
• • （一）题目分析
  • （二）代码展示
• 三、查找总价格为目标值的两个商品
• • （一）题目分析
  • （二）代码展示
• 四、总结

（一）盛水最多的容器

点击跳转

（一）题目分析

设置两个指针分别指向最左边和最右边，首先记录一个最大盛水量 max = 0，每次舍弃掉两个指针中较小的那一个（舍弃的指针和中间的每一个组成的容器都小于当前值，因此可以舍弃），这个过程中一定要维护最大值max。

（二）代码展示

class Solution {public: int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1; int max = 0; while (left < right) { int min_side = height[left] < height[right] ? height[left] : height[right]; int temp = (right - left) * min_side; if (temp > max) max = temp; min_side == height[left] ? left++ : right--; } return max; }};

二、有效的三角形个数

点击跳转

（一）题目分析

判断是否可以组成三角形，可以直接判断最小的两条边是否大于第三边。因此，我们仅仅需要将数组排序，依次固定数组中的最大值，观察它可以组成三角形。
在判断另外两条边时，也只需要创建一组对撞指针，找到符合要求的目标值。

（二）代码展示

class Solution {public: int triangleNumber(vector<int>& nums) { int cur = nums.size() - 1, ret = 0; sort(nums.begin(), nums.end()); while (cur > 1) { int left = 0, right = cur - 1; while (left < right) { if(nums[left] + nums[right] > nums[cur])  {  ret += right - left;  right--; } else{  left++; } } cur--; } return ret; }};

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

点击跳转

（一）题目分析

这道题相比上到题目更加简便，用对撞指针查找目标值即可，有一个返回值的小技巧，使用initalizer_list 对象做返回值，不同在单调创建vector对象。

（二）代码展示

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}; }};

四、总结

想要在一段有序的数组区间中查询目标值，可以采用对撞指针。亦或者在盛水最大的容器中，有一种单调性在里边，也可以采取对撞指针。