双指针算法介绍：
该算法涉及到使用俩个指针来来遍历数组，通过俩个指针的协调工作，能大大的提高代码效率，有效的减少时间复杂度，提高代码性能。
双指针算法包括快慢指针，前后指针，或者可以搭配单调性来很好的解决问题。本文将利用Java语言来实现双指针的常见题型。
一、快乐数（. - 力扣（LeetCode））
难度：简单
题目解法分析：
如上图所述，题目大致意思为将所给数的每个位上的数分别平方，再相加：
例如题目的俩道例题，可以看到，一个是无线循环其他数，一个是可以无线循环1。所以解题的思想在于该如何从成环的这些数入手。
算法思想：
代码实现：
public static int isSum(int n){
int sum = 0;
while(n != 0){
sum += Math.pow(n%10,2);
n /= 10;
}
return sum;
}
public boolean isHappy(int n) {
int slow = isSum(n);//充当慢指针（先执行一步）
int fast = isSum(slow);//充当快指针（基于慢指针再执行一步，相当于俩步）
while(slow != fast){
//慢指针执行一步
slow =isSum(slow);
//快指针执行俩步
fast = isSum(isSum(fast));
}
return fast == 1;
}
二、三数之和（. - 力扣（LeetCode））
难度：中等
题目解法分析：
如图所述，找出一个数组中三个和为0的数，且下标不一，且每个三元组都不能有一一对应的重复元素（如【-1,0,1】和【0，-1,1】就不可以）
所以解决该题则需要注意去重操作，为了提高效率和解决问题的麻烦，所以我们得需要先排个序，然后再以固定一个数和双指针算法来实现。
算法思想：
代码实现：
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> S = new ArrayList<>();//用于返回所有三元组
Arrays.sort(nums);//排序
//假设先固定最左边的数，然后依次往右遍历
int n = nums.length;
int flg = 0, left = 0, right = 0, num = 0;//初始化左右指针，固定数的相反值,和左右指针数值之和
for (int i = 0; i < n; ) {
//这里包含着一个小优化，当前值大于零时，由于数组单调递增，则可以直接返回
if(nums[i] > 0){
break;
}
left = i+1;
right = n-1;
flg = -nums[i];
//利用单调性和双指针算法来找出符合的另外俩个数
while(left < right){
num = nums[left] + nums[right];
//判断是否小于目标值
if(num < flg){
left++;
}
else if(num > flg){
right--;
}
//注意：一般是找到三元组后才查重，避免重复添加
else{
S.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));//找到三元组后添加
left++;
right--;
//查重操作
//left查重
while(left < right && nums[left] == nums[left -1]){
left++;
}
//right查重
while(left < right && nums[right] == nums[right +1]){
right--;
}
}
}
//先找完一个三元组，再进行i的查重
i++;
while(i < n && nums[i] == nums[i-1]){
i++;
}
}
return S;
}
三、盛最多水容器（. - 力扣（LeetCode））
难度：中等
题目解法分析：
如图所述，该题是让我们求出在俩端柱子内最大的容积面积，容积面积公式为V=Sh。
该题可设底面积为宽度，然后用宽度来乘以俩端中最低限度的高度，返回最大容积。
该题主要是利用双指针结合单调性，来解决最大容积问题。
算法思想：
定义左右指针，比较左右端点大小，因为最小的为限制，所以最小的往前（后）走，每次记录左右端点时的容积，比较最大值
若是当前左端点小于等于前一个左端点，由单调性可知，则直接跳过，右端点也一样
代码实现：
public int maxArea(int[] height) {
int left =0;
int right = height.length -1;
int max = 0;//记录最大容积
while(left < right){
//比较左右最小值，以最小值为限制来乘以宽来获得当前容积
int v = Math.min(height[left],height[right]) *(right - left);
max = Math.max(max,v);//比较当前容积和之前容积的最大值来更新
//左端小于右端，最小的为限制，所以要走一步
if(height[left] < height[right]){
left++;
}
else{
right--;
}
}
return max;
}
时间复杂度：O（N）
空间复杂度：O（1）
四、接雨水（. - 力扣（LeetCode））
难度：困难
题目解法分析：
如图所述，我们可以看到，在每一个凹槽中都会有宽度为1的水单位，由于高度限制所以水单位的个数也会有所限制。
给定一个数组，数组中每个数代表的是柱子的高度，根据木桶效应可知凹槽中的水都会由俩端中最矮的那个柱子为基准来计算水单位，因此我们需要判断俩端柱子的高低位从而判断能装多少水（只有凹槽才能装水）
柱子的高低有以下的几种可能：
可以看到，只有第三和第四俩幅图才有凹槽可以装水，第三幅图以左端为基准，第四副图以右端为基准。
所以我们需要判断是左右端点哪边大哪边小，中间的柱子是否比俩端柱子矮。
算法思想：
1.定义一个用来计算水单位的数count
2.定义一个左右指针left，right，来判断左右俩端柱子的高度，再比较左右俩边高度的大小，定义一个左边最高度和右边最高度left_max,right_max。
3.需要一次循环，内部包含判断语句，来判断左右俩边的走向和积水量
代码实现：
public int trap(int[] height) {
int count = 0;//用来计数
int left = 0;
int right = height.length - 1;
int left_max =0,right_max =0;//左右端点最大数
//双指针遍历
while(left<right){
//左端点高度比右端点小
if(height[left] < height[right]){
//更新最大数
if(height[left] > left_max){
left_max = height[left];
}
//有坑的话，则计算水单位
//需要注意的是：当第一个数为0时，该数积不了水，且最大数初始化
//都是为零，所以0-0还是为零（所以此处不做修改），直到遇到高度不为零才真正能积水
else{
count += left_max - height[left];
}
left++;//左指针往后走
}
//右端点小于等于左端点，和上述步骤一样
else{
if(height[right] > right_max){
right_max = height[right];
}
else{
count += right_max - height[right];
}
right--;//右指针往前走
}
}
return count;
}
时间复杂度：O（N）
空间复杂度：O（1）
这题虽然被标上了困难，但实际上还没有那么困难的♪(･ω･)ﾉ（不过一开始我也是用暴力解法才解出来，时间复杂度高达O（N^2）o(╥﹏╥)o 空间复杂度也是一言难尽 o(╥﹏╥)o）
