什么时候用双指针？
在我们遇到像数组，链表这类数据结构的算法题目的时候，应该要想得到双指针的套路来解决问题。
特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。
链表这种数据结构也是树形结构和图的原型，所以有时候在关于图和树形结构的算法题目中也会用到双指针。
当你遇到此类数据结构，尝试使用双指针来解题的时候，可以从以下几个双指针类题目的套路入手进行思考。
快慢指针
类似于龟兔赛跑，两个链表上的指针从同一节点出发，其中一个指针前进速度是另一个指针的两倍。
利用快慢指针可以用来解决某些算法问题，比如：
1：计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。
2：判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。
3：判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
4：求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了
5：求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）
碰撞指针
一般都是排好序的数组或链表，否则无序的话这两个指针的位置也没有什么意义。
特别注意两个指针的循环条件在循环体中的变化，小心右指针跑到左指针左边去了。常用来解决的问题有：
1： 二分查找问题
2：n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。
滑动窗口法
两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。这类问题一般包括：
1：字符串匹配问题
2：子数组问题如果有其它的想法
双指针求最大容积
这道题其实比较简单，因为你很容易就能想到要求最大面积，那么只需要宽最大的时候，高最高即可。并且如果你想要换取高度，你基本是一定要牺牲宽度的，因为只有选择修改宽度，你才能得到新的高度，那么我们需要权衡的就是，在两个高移动的过程中，我们应该尽可能的保证移动的是矮的那边的高。
public int maxArea(int[] height) { int left = 0; //左指针 int right = height.length - 1; //右指针 int v = 0; //最后面积 int high = 0; //当前高 木桶效应影响 int width = 0; //当前宽 while (left < right) { high = Math.min(height[left], height[right]); //木桶效应得到最小的那根短板 width = right - left; //得到当前宽 if (v < high * width) { //判断移动之后是否有更大的体积，有才保留 v = high * width; } if (height[right] > height[left]) { //判断左边还是右边更短 移动更短的那一边 left++; } else { right--; } } return v; }
删除有序数组重复数据
有一个特别重要的前提，这个数组是有序的，也因为他的有序，所以我们保证每次只保存第一个遇到的数据即可，如果下一个数据和这个数据相等，我们直接跳过即可，直到遇到下一个不相等的数据。
// public int removeDuplicates(int[] nums) { // int n = nums.length; // if (n == 0) { // return 0; // } // int fast = 1, slow = 1; // while (fast < n) { // if (nums[fast] != nums[fast - 1]) { // nums[slow] = nums[fast]; // ++slow; // } // ++fast; // } // System.out.println(Arrays.toString(nums)); // return slow; // } public int removeDuplicates(int[]nums){ Set<Integer> set = new LinkedHashSet<>(); for (int num : nums) { set.add(num); } int i=0; for (Integer integer : set) { nums[i++]=integer; } return set.size(); }
移除指定元素
这道题我们需要做的是遍历元素，并且删除指定的数据，那么与上一题一样，我们可以设定两个指针，第一个指针指向插入数据的索引，第二个指针进行遍历，如果第二个指针遇到的值等于val，那么就跳过这个值，如果遇到的不是val，那么就正常的放入到第一个指针指向的索引的位置进行覆盖即可。
public int removeElement(int[] nums, int val) { int slow = 0;//双指针 slow代表的是非val值可以插入的下一个位置 int fast = 0;//fast用于遍历 int n=nums.length; while (fast<n){ if (nums[fast]!=val){ nums[slow++]=nums[fast]; } fast++; } return slow; }
合并两个有序数组或链表
特殊的点在于我们需要把数据放入到第一个数组的尾巴，如果说是返回一个新的数组，那么这道题就更加简单了。
不过这样子也没有提升多大的难度，我们只需要把从头遍历换为从尾巴遍历即可。
依旧是使用双指针，他们分别去遍历两个数组，然后在创建一个索引指针，这个索引指针用来指向两个数组中的数据应该插入的位置。
public void merge(int[] nums1, int m, int[] nums2, int n) { int p1 = m - 1, p2 = n - 1; int tail = m + n - 1; int cur; while (p1 >= 0 || p2 >= 0) { if (p1 == -1) { cur = nums2[p2--]; } else if (p2 == -1) { cur = nums1[p1--]; } else if (nums1[p1] > nums2[p2]) { cur = nums1[p1--]; } else { cur = nums2[p2--]; } nums1[tail--] = cur; } }
那么合并两个有序链表也是一样的操作。
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; return prehead.next; }
两个数组的交集
暴力Set+Stream流解决
public static int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); for (int num : nums1) { set1.add(num); } for (int num : nums2) { set2.add(num); } Object[] objects = set1.stream().filter(x -> set2.contains(x)).toArray(); int[] arr = new int[objects.length]; int index= 0; for (Object o : objects) { arr[index++]= (int) o; } return arr; }
当然，考虑到是遍历两个数组，那么我们也可以考虑到使用双指针。
但是数据是无序的，如果使用双指针，那么我们估计就是要暴力的去遍历两个数组了，那么时间复杂度估计是O(mn)，所以我们先使用快排对数据进行排序。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre
pre 表示上一次加入答案数组的元素。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre ，将该数字添加到答案并更新 pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int length1 = nums1.length, length2 = nums2.length; int[] intersection = new int[length1 + length2]; int index = 0, index1 = 0, index2 = 0; while (index1 < length1 && index2 < length2) { int num1 = nums1[index1], num2 = nums2[index2]; if (num1 == num2) { // 保证加入元素的唯一性 if (index == 0 || num1 != intersection[index - 1]) { intersection[index++] = num1; } index1++; index2++; } else if (num1 < num2) { index1++; } else { index2++; } } return Arrays.copyOfRange(intersection, 0, index); }
当然，更快的方法好像就是O（mn）了，实际上，可以先用Set去重，然后用contains函数判断两个Set集合中是否用重复值，最后再把这个set集合拷贝到数组中即可。
public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<Integer>(); Set<Integer> set2 = new HashSet<Integer>(); for (int num : nums1) { set1.add(num); } for (int num : nums2) { set2.add(num); } return getIntersection(set1, set2); } public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) { if (set1.size() > set2.size()) { return getIntersection(set2, set1); } Set<Integer> intersectionSet = new HashSet<Integer>(); for (int num : set1) { if (set2.contains(num)) { intersectionSet.add(num); } } int[] intersection = new int[intersectionSet.size()]; int index = 0; for (int num : intersectionSet) { intersection[index++] = num; } return intersection; }
