什么时候用双指针？

引用

在我们遇到像数组，链表这类数据结构的算法题目的时候，应该要想得到双指针的套路来解决问题。
特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。
链表这种数据结构也是树形结构和图的原型，所以有时候在关于图和树形结构的算法题目中也会用到双指针。
当你遇到此类数据结构，尝试使用双指针来解题的时候，可以从以下几个双指针类题目的套路入手进行思考。

快慢指针

类似于龟兔赛跑，两个链表上的指针从同一节点出发，其中一个指针前进速度是另一个指针的两倍。
利用快慢指针可以用来解决某些算法问题，比如：

1：计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。

2：判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。

3：判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

4：求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了

5：求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）

碰撞指针

一般都是排好序的数组或链表，否则无序的话这两个指针的位置也没有什么意义。
特别注意两个指针的循环条件在循环体中的变化，小心右指针跑到左指针左边去了。常用来解决的问题有：
1： 二分查找问题
2：n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。

滑动窗口法

两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。这类问题一般包括：
1：字符串匹配问题
2：子数组问题如果有其它的想法

双指针求最大容积

LeetCode原题
这道题其实比较简单，因为你很容易就能想到要求最大面积，那么只需要宽最大的时候，高最高即可。并且如果你想要换取高度，你基本是一定要牺牲宽度的，因为只有选择修改宽度，你才能得到新的高度，那么我们需要权衡的就是，在两个高移动的过程中，我们应该尽可能的保证移动的是矮的那边的高。

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;}

删除有序数组重复数据

LeetCode原题
有一个特别重要的前提，这个数组是有序的，也因为他的有序，所以我们保证每次只保存第一个遇到的数据即可，如果下一个数据和这个数据相等，我们直接跳过即可，直到遇到下一个不相等的数据。

// 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();}

移除指定元素

LeetCode原题
这道题我们需要做的是遍历元素，并且删除指定的数据，那么与上一题一样，我们可以设定两个指针，第一个指针指向插入数据的索引，第二个指针进行遍历，如果第二个指针遇到的值等于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;}

合并两个有序数组或链表

LeetCode原题
特殊的点在于我们需要把数据放入到第一个数组的尾巴，如果说是返回一个新的数组，那么这道题就更加简单了。
不过这样子也没有提升多大的难度，我们只需要把从头遍历换为从尾巴遍历即可。
依旧是使用双指针，他们分别去遍历两个数组，然后在创建一个索引指针，这个索引指针用来指向两个数组中的数据应该插入的位置。

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;}}

LeetCode合并有序链表
那么合并两个有序链表也是一样的操作。
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

 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;}

两个数组的交集

LeetCode

暴力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;}