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

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

（一）盛水最多的容器

点击跳转

（一）题目分析

设置两个指针分别指向最左边和最右边，首先记录一个最大盛水量

max = 0

，每次舍弃掉两个指针中较小的那一个（舍弃的指针和中间的每一个组成的容器都小于当前值，因此可以舍弃），这个过程中一定要维护最大值max。

（二）代码展示

classSolution{public:intmaxArea(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;}};

二、有效的三角形个数

点击跳转

（一）题目分析

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

（二）代码展示

classSolution{public:inttriangleNumber(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

对象。

（二）代码展示

classSolution{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++;elseif(price[left]+ price[right]> target) right--;elsereturn{price[left], price[right]};}return{-1,-1};}};

四、总结

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