双指针技能总结
https://labuladong.gitee.io/algo/2/21/53/
看完这篇文章，你不仅可以学习算法例程，还可以去LeetCode获取以下问题：
11.环形链表(简单)
12.环形链表二(简单)
17.两个数的和-输入有序数组(中)
34.反转字符串(简单)
19.删除链表的倒数第n个元素(中)
86.链表的中间节点
———
我把双指针技术分为两类，一类是“快指针”，一类是“左指针”。前一种解决方案主要解决链表中的问题，比如链表是否包含环的典型判定；后者主要解决数组(或字符串)中的问题，比如二分搜索法。
一、快慢指针的常见算法
通常，快指针和慢指针被初始化为链表的头节点。向前移动时，快指针第一，慢指针第二，巧妙地解决了链表中的一些问题。
1.确定链表中是否有环。
这是链表最基本的操作，学习数据结构要熟悉这个算法思想。
单链表的特点是每个节点只知道下一个节点，用指针判断链表中是否有环是不可能的。
如果链表中没有环，那么这个指针最终会遇到一个空指针null，表示链表结束了。也就是说，可以判断链表不包含环：
布尔hasCycle(列表节点头){ 0
趁着(头！=null)
head=head.next
返回false
}
但是如果链表中有一个环，那么这个指针就会陷入无限循环，因为环数组中没有空指针作为尾节点。
经典的解决方案是用两个指针，一个快，一个慢。如果没有环，运行快的指针最终会遇到null，表示链表不包含环；如果有一个环，那么快指针最终会比慢指针超出一个圈，慢指针会相遇，表示链表包含一个环。
力的推演第141题就是这个问题，解答代码如下：
布尔hasCycle(列表节点头){ 0
ListNode快，慢；
快=慢=头；
趁着(快！=null fast.next！=null){ 0
fast=fast . next . next；
慢=慢。下一步；
if (fast==slow)返回true
}
返回false
}
2.如果知道链表中有一个环，返回这个环的起始位置。
这是李口的142号问题。其实一点都不难。有点像脑筋急转弯。先直接看代码：
列表节点检测周期(列表节点头){ 0
ListNode快，慢；
快=慢=头；
趁着(快！=null fast.next！=null){ 0
fast=fast . next . next；
慢=慢。下一步；
if(fast==slow)break；
}
//上面的代码类似于hasCycle函数。
if(fast==null | | fast . next==null){ 0
//fast遇到指示没有环的空指针。
返回null
}
慢=头；
虽然(慢！=快速){ 0
fast=fast.next
慢=慢。下一步；
}
回归缓慢；
}
可以看出，当快指针和慢指针相遇时，让任一指针指向头节点，然后让它们以相同的速度向前移动，它们再次相遇的节点位置就是环开始的位置。为什么呢？
第一次见面时，假设慢指针慢已经走了k步，那么快指针快肯定已经走了2k步：
快一定比慢多了k步。额外的k步实际上意味着快速指针在环中盘旋，因此k的值是环长度的“整数倍”。
对了，以前有过。
读者争论为什么是环长度整数倍，我举个简单的例子你就明白了，我们想一想极端情况，假设环长度就是 1，如下图：
那么fast肯定早早就进环里转圈圈了，而且肯定会转好多圈，这不就是环长度的整数倍嘛。
言归正传，设相遇点距环的起点的距离为m，那么环的起点距头结点head的距离为k - m，也就是说如果从head前进k - m步就能到达环起点。
巧的是，如果从相遇点继续前进k - m步，也恰好到达环起点。你甭管fast在环里到底转了几圈，反正走k步可以到相遇点，那走k - m步一定就是走到环起点了：
所以，只要我们把快慢指针中的任一个重新指向head，然后两个指针同速前进，k - m步后就会相遇，相遇之处就是环的起点了。
3、寻找链表的中点
类似上面的思路，我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
力扣第 876 题就是找链表中点的题目，解法代码如下：
ListNode middleNode(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// slow 就在中间位置
return slow;
}
当链表的长度是奇数时，slow恰巧停在中点位置；如果长度是偶数，slow最终的位置是中间偏右：
寻找链表中点的一个重要作用是对链表进行归并排序。
回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。对于链表，合并两个有序链表是很简单的，难点就在于二分。
但是现在你学会了找到链表的中点，就能实现链表的二分了。关于归并排序的具体内容本文就不具体展开了。
4、寻找链表的倒数第n个元素
这是力扣第 19 题「删除链表的倒数第n个元素」，先看下题目：
我们的思路还是使用快慢指针，让快指针先走n步，然后快慢指针开始同速前进。这样当快指针走到链表末尾null时，慢指针所在的位置就是倒数第n个链表节点（n不会超过链表长度）。
解法比较简单，直接看代码吧：
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast, slow;
fast = slow = head;
// 快指针先前进 n 步
while (n-- 0) {
fast = fast.next;
}
if (fast == null) {
// 如果此时快指针走到头了，
// 说明倒数第 n 个节点就是第一个节点
return head.next;
}
// 让慢指针和快指针同步向前
while (fast != null fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// slow.next 就是倒数第 n 个节点，删除它
slow.next = slow.next.next;
return head;
}
二、左右指针的常用算法
左右指针在数组中实际是指两个索引值，一般初始化为left = 0, right = nums.length - 1。
1、二分查找
前文二分查找框架详解有详细讲解，这里只写最简单的二分算法，旨在突出它的双指针特性：
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left = right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] target)
left = mid + 1;
else if (nums[mid] target)
right = mid - 1;
}
return -1;
}
2、两数之和
直接看力扣第 167 题「两数之和 II」吧：
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节left和right可以调整sum的大小：
int[] twoSum(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 题目要求的索引是从 1 开始的
return new int[]{left + 1, right + 1};
} else if (sum target) {
left++; // 让 sum 大一点
} else if (sum target) {
right--; // 让 sum 小一点
}
}
return new int[]{-1, -1};
}
3、反转数组
一般编程语言都会提供reverse函数，其实非常简单，力扣第 344 题是类似的需求，让你反转一个char[]类型的字符数组，我们直接看代码吧：
void reverseString(char[] arr) {
int left = 0;
int right = arr.length - 1;
while (left right) {
// 交换 arr[left] 和 arr[right]
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; right--;
}
}
4、滑动窗口算法
这也许是双指针技巧的最高境界了，如果掌握了此算法，可以解决一大类子字符串匹配的问题，不过「滑动窗口」稍微比上述的这些算法复杂些。
不过这类算法是有框架模板的，而且前文我写了首诗，把滑动窗口算法变成了默写题就讲解了「滑动窗口」算法模板，帮大家秒杀几道子串匹配的问题，如果没有看过，建议去看看。
＿＿＿＿＿＿＿＿＿＿＿＿＿
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/84603.html