一，什么是双指针
????????双指针大致可分为两类，一类是 "快慢指针"，一类是 "左右指针"。
????????"快慢指针" --> 解决链表中的问题 (比如，寻找链表中点，判断链表是否有环等)
????????"左右指针" --> 解决数组中的问题 (比如，二分搜索，有序数组去重，滑动窗口等)
二，快慢指针
????????快慢指针初始化时都指向链表的表头，快指针(fast)每次走 2 步，慢指针(slow)每次走 1 步。
????????因为每次 fast 都比 slow 多走 1 步，当达到停止条件时， fast 所走过的节点数是 slow 的两倍。
????????对于停止条件：
????????????????若是无环链表，fast 走到 nullptr 时即停止，此时 fast 走完了整个链表，故 slow 停在了链表的中点。
????????????????若是有环链表，fast 和 slow 最终会相遇，而相遇时 fast 比 slow 正好多走了环的整数圈。
??????? a, 判断链表是否有环
????????b, 若有环，找到环的起点
????????c, 若无环，找到链表的中点
????????d, c 的升级版，找到无环链表的倒数第 k 个节点
a, 判断链表中是否有环
判断的依据在于，若是无环，则 fast 一定会走到链表尾部; 若是有环，则 fast 和 slow 一定会相遇。
bool hasCycle(Node* head) {
Node* fast = head;
Node* slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // 若相遇，则说明该链表有环
return true;
}
}
return false;
}
b, 寻找有环链表中环的起点
有环链表，环的起点是 3 。
1 -> 2 -> 3 -> 4 -> 5
^ |
| v
8 -> 7 -> 6
先看代码
Node* findStartNode(Node* head) {
Node* fast = head;
Node* slow = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) { // 先找到二者相遇的节点
break;
}
}
// 此时 slow 与 fast 两个节点相遇了
slow = head; // 让 slow 再指向 head
while (slow != fast) { // 让两个指针以相同的速度前进，再次相遇时便是环的起点
slow = slow->next;
fast = fast->next;
}
return slow;
}
第一部分代码无需解释，就是两者第一次相遇。
需要理解的是，为何第一次相遇后，让其中一个指针从头开始与另外一个指针以相同速度前进，二者再次相遇时便是环的起点?
假设第一次相遇时， slow 走了 k 个节点，那么 fast 一定走了 2k 个节点。也就是说 fast 比 slow 多走了 k 步(环长度的整数倍)。
我们再假设，从 head 走到环的起点需要 m 步。那么第一相遇时， slow 已经在环里走了 k-m 步。(同理，fast 也相当于从环的起点走了 k-m 步)
第一次相遇后，我们让 slow 指向 head，然后让 slow 和 fast 以相同速度继续走，会发现，当走 m 步后， slow 会走到环的起点，而 fast 也正好走到环的起点。(fast : k-m+m = k)
所以它们第二次相遇的地点便是环的起点。
c, 寻找无环单链表的中点
这个就比较简单了，直接让 fast 走到 nullptr，此时 slow 所在的节点便是链表的中点
需要注意的是，链表节点为奇数或偶数时的不同情况。
奇数: 1 -> 2 -> 3 -> 4 -> 5 -> nullptr slow : 3 , fast : 5
偶数: 1 -> 2 -> 3 -> 4 -> nullptr slow : 3 , fast : nullptr
寻找中点的作用 : 在链表的归并排序中需要用到
Node* getMiddleNode(Node* head) {
Node* fast = head;
Node* slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
d, 寻找单链表的倒数第 k 个元素
这个与寻找链表的中点是一样的，先让 fast 指针先跑 k 步，然后让 slow 和 fast 以同样速度跑。
等 fast 跑到尾部时， slow 就处于倒数第 k 个元素了。(我们假设链表的长度大于 k)
Node* getNode(Node* head, int k) {
Node* fast = head;
Node* slow = head;
while (k-- && fast) {
fast = fast->next;
}
while (fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
三，左右指针
????????左右指针一般运用在数组问题中，实际是两个索引值，一般初始化为 left = 0, right = nums.size() - 1;
????????a, 二分查找 (见 : 10. 二分搜索算法)
????????b, 有序数组去重 (leetcode 链接 : 26. Remove Duplicates from Sorted Array)
??????? c, 反转数组
??????? d, 滑动窗口 (见 : 11. 滑动窗口)
a, 二分查找
在升序的数组中找到目标值，并返回其下标，若无，则返回 -1。
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) { // 注意，此处是 <=
int mid = left + (right - left) >> 1; // 注意， mid = (left + right) / 2; 可能导致越界
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
b, 有序数组去重
给定一个有序的数组，其中可能存在连续相同的数字，要求原地删除重复的元素并返回删除后数组的长度。(注，空间复杂度要求 O(1))
比如 , input : [1, 2, 2, 3, 4, 4, 6, 8]
output : [1, 2, 3, 4, 6, 8]
return : 6
int removeDuplicates(vector<int>& nums) {
int left = 0, right = 0;
int size = nums.size();
if (size) {
while (right < size) {
if (nums[right] != nums[left]) {
nums[++left] = nums[right];
}
right++;
}
left++; // 最后返回的是长度，故需要再 +1
}
return left; // 若 size == 0, 则直接返回 0
}
c, 反转数组
将数组内的元素反转
void reverse(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++; right--;
}
}
d, 滑动窗口
可以解决一大类字符串匹配的算法。
|