前言
小伙伴们，你们好呀！我是老寇！
双指针算法是基于暴力解法的优化，将时间复杂度降低到线性。
双指针算法与其说是一种算法，不如说是一种技巧，它能够缩短循环遍历的时间，提高程序的运行速度！
双指针分为两类，快慢指针和左右指针：
1.快慢指针（弗洛伊德循环查找算法），类似龟兔赛跑。
2.左右指针又称指针碰撞，就是一左一右遍历。
注：多练习，印象才更深刻
正文
快慢指针
快乐数
class Solution { public boolean isHappy(int n) { int slow = n,fast = n; do{ slow = bitSquareSum(slow); fast = bitSquareSum(fast); fast = bitSquareSum(fast); } while(slow != fast); return (slow == 1); } private int bitSquareSum(int x) { int sum = 0,cur; while(x > 0) { cur = x % 10; x = x / 10; sum += cur * cur; } return sum; } }
结论：较哈希集，指针只需要常数的额外空间
删除有序数组中的重复项
class Solution { public int removeDuplicates(int[] nums) { int len = nums.length; if(len < 2) { return len; } int j = 0; for(int i = 0; i < len; i++) { if(nums[j] != nums[i]) { nums[++j] = nums[i]; } } return j + 1; } }
结论：找对「循环不变量」是做题的关键，我理解的循环遍历是一个if条件，在本题中nums[j]是慢指针，负责数据的替换，nums[i]是快指针，负责数据的遍历。
左右指针
反转字符串
class Solution { public void reverseString(char[] s) { int left = 0,right = s.length - 1; char c; while(left < right) { c = s[left]; s[left] = s[right]; s[right] = c; left++;right--; } } }
结论：较套用两层for循环，所要的时间快一点
双指针范式（作者总结）
//举栗子 数组n1,n2 //1.排序 Arrays.sort(n1); Arrays.sort(n2); //数组索引从0开始 int index = 0,index1 = 0,index2 = 0; //开辟数组 int len1 = n1.length,len2 = n2.length; int[] arr = new int[Math.min(n1,n2)]; //指针动起来 while(index1 < len1 && index2 < len2) { if(两个值相等) { index1++; index2++; arr[index++] = 其中一个值 } else if (第一个值大) { index2++; } else { //第二个值大 index1++; } } //谁小谁加+1
