算法之双指针系列1

目录

一：双指针的介绍

1：快慢指针

2：对撞指针

二：对撞指针例题讲述

---

一：双指针的介绍

在做题中常用两种指针，分别为对撞指针与快慢指针。

1：快慢指针

简称为龟兔赛跑算法，它的基本思想是使用两个移动速度不同的指针在数组或链表等序列结构上移动。

这种对于处理环形链表和数组以及循环重复问题，是非常好用的。

2：对撞指针

简称为左右指针，它的基本思想是一个指针从最左端开始，一个从最右端开始，逐渐往中间逼近。一般终止条件是两个指针相遇或者错开。

一般用于顺序结构中。

注意：这里的指针并不是C语言中的指针，而是指在数组中设置的两个下标，通过改变两个下标来改变所在数组的位置。

二：对撞指针例题讲述

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

1：盛最多水容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

算法原理：

解法1：暴力枚举，是很简单的，但是我们可以发现他的时间复杂度是超时的。

解法2：双指针法，题中让求v,那么v=h*w.

1

8

6

2

5

4

8

3

7

就以上面的数组举例。

我们设左指针left为数组最左边的下标，右指针right为数组最右边的下标。

那么我们要取最大的V只有一种情况，就要h变大，w变小。（因为最开始的W最大）。

int n=height.size();
int left=0,right=n-1;设置左右指针。
int ret=0;
while(left<right)
{int sum=min(height[left],height[right])*(right-left) //求vret=max(ret,sum)//求出最大的v.if(height[left]<height[right])left++;elseright--;}
return ret;

 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2:有效三角形的个数

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

示例 1:

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

需要的判断条件就是两个最小边之和大于最大边。

算法原理：

第一种:暴力求解。明显的是超出时间限制的。

第二种：双指针 。利用单调性。

1.先固定最大的数。

2.在最大的数的左区域内，使用双指针算法，快速统计出符合要求的三元组的个数。

sort(nums.begin(),nums.end());//这一步是排序。
int n=nums.size();
int i=n-1;
int ret=0;for(i;i>=2;i--){int left=0;int right=i-1;while(left<right)//基本条件{ if(nums[left]+nums[right]<=nums[i]) left++;else  {ret+=right-left;right--;}}}
return ret;}

 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

算法思路

1：暴力枚举。显然还是超过时间限制。

2：双指针。比较简单就不再详解。

 int left = 0, right = nums.size() - 1;while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else return {nums[left], nums[right]};}// 照顾编译器return {-4941, -1};