一.双指针算法介绍
概念：双指针是指在遍历数据结构（如数组、链表等）时使用两个指针，通过特定的移动规则来解决问题。这两个指针可以同向移动，也可以相向移动。
- 同向双指针：常用于解决需要两个位置信息的问题。例如，在一个有序数组中查找两个数的和等于目标值的情况。一个指针从数组头部开始，另一个指针从当前指针的后面开始，通过不断调整指针位置来找到符合条件的数对。
- 相向双指针：典型应用是在排序数组中查找满足某种条件的子数组。比如，在一个递增的数组中，一个指针从数组开头，一个指针从数组末尾，根据两个指针所指元素的和、差等关系，向中间移动指针，直到满足特定条件。
- 优势：双指针算法可以降低时间复杂度，将原本需要嵌套循环的问题简化为单循环或更高效的遍历方式。例如，在某些情况下，可以将时间复杂度从n^2 降低到n 。
二.移动0
题目链接
class Solution {public void moveZeroes(int[] nums) {for(int cur = 0,dest = -1;cur<nums.length;cur++){if(nums[cur]!=0){dest++;int tmp = nums[cur];nums[cur]=nums[dest];nums[dest] =tmp;}}}
}
解题思路：主要把数组分为3个区间，已经处理过的非0区间，0元素区间和未处理的区间。
把数组分为3部分：
- [0,dest] :处理过的非0元素
- [dest+1,cur-1] 处理过的0元素
- [cur,arry,length-1] 未被处理的元素
初始化时让cur 指向0元素位置，dest指向-1。刚开始所有元素都未处理，按照划分区间，未被处理的元素区间为【0，dest】，所以dest不能等于0，等于0说明第一个元素已经被处理过，边界不好区分，因此让dest=-1。
当cur的值等于0时，cur++;cur的值不等于0，让dest先走一步接着dest和cur 对应元素的值互相交换，每次都能保证数组的3个范围的划分。
在代码执行中，非零元素会依次覆盖零元素的位置，最终达到将所有零移动到数组末尾的目的。此方法的时间复杂度为 O(n)，空间复杂度为 O(1)，即为原地操作，不占用额外空间。如果暴力求解时间复杂度n方，双指针确实比暴力求解时间复杂度低。
三.快乐数
快乐数
class Solution {public int Num(int n) {int sum = 0;while (n!= 0) {int t = n % 10;sum += t * t;n /= 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = Num(n);while (fast!= slow) {slow = Num(slow);fast = Num(Num(fast));}return slow == 1;}
}解法：前面学习链表的时候我们学过判断链表是否带环，让快指针一次走2步，慢指针一次走一步，如果存在环它们总能相遇。
以19为例是该树快乐数，通过对19的运算结果确实是1，说明是快乐数。
以2为例判断不是快乐数。4和20形成了一个环，说明不是快乐数。
把这个环想象成链表带环，让快指针在环里面一次走2步，慢指针一次走一步总会在环里面的某个位置相遇，相遇后跳出循环判断相遇点的值是否为1，如果是1说明是快乐数，不是1说明不是。
关于是否会陷入死循环
在这个算法中，实际上是利用了快慢指针的思想。对于一个正整数，如果它不是快乐数，那么在不断计算各位数字平方和的过程中，最终会陷入一个循环。
由于数字的范围是有限的（对于给定的正整数，经过有限次的数字平方和计算后，得到的结果一定在一个有限的范围内）。
假设存在一个非快乐数，在计算过程中会进入一个循环，那么快慢指针一定会在这个循环中相遇。因为快指针每次移动两步，慢指针每次移动一步，在一个有限的循环中，快指针必然会追上慢指针。
如果这个数是快乐数，那么最终会得到1，此时快慢指针也会相等（因为最终都会到达1这个结果）。
四.盛最多容器的水
盛最多容器的水
class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int v = 0;while (left < right) {int min = Math.min(height[left], height[right]);v = Math.max(v, min*(right - left));if (height[right] > height[left]) {left++;} else {right--;}}return v;}
}
解法：如果本题暴力求解去枚举算最大值比较大小，那么时间复杂度太高。
简单方法是去掉一些没必要的值。举个例子：算8和5的容积。该容器高度是5，宽度为（right-left）=6。因此v=5*6=30。
接着枚举该数组v的最大值那么宽度必然是减少的,因为求下一个容积会让left++，或者right–,那么（right-left）的值必然减少。因此宽度会减少。
对于v=宽度*高度，宽度减少要想体积增大必须高度增加。8和5的最小值是5,要想高度增加，那么right的值必然要大于5,所以可以看做舍弃5,让right减减。计算容器8和9容积
v=5*8=40，v上次的值是30,40大于30,所以v的值更新为40。求下一个容积也是同样的做法，要想v在宽度减少的情况下增大，那么高度的最小值一定要增大，也就是比较left和right的对应值的最小值，把这个最小值舍弃掉，在去求v。每次比较和上次v值的大小看是否更新v的值。
这道题考察了如何通过合理的指针移动来减少不必要的计算，双指针法的精髓在于每次有目的地舍弃一些不可能产生最大值的组合，从而将时间复杂度降至线性。在实际解题时，双指针法是一种非常高效的解法，特别适用于涉及到对区间或边界的遍历优化问题。