leedcode-双指针
双指针简介
分为两类：
- 快慢指针：主要解决链表中的问题
- 左右指针：主要解决数组 / 字符串中的问题
快慢指针
- 判断链表中是否含有环
- 借助哈希表（判断哈希表中是否含有当前节点）
- 使用快慢指针（快指针每次走两步，如果有环，二者会相遇）
- 已知链表中含有环，返回这个环的起始位置
思路：
- 先寻找快慢指针相遇的点
- 当二者相遇时，让其中一指针指向头节点，然后以相同的速度前进，再次相遇时所在的节点位置就是环开始的位置
证明：
- 第一次相遇，假设 slow 走了 k 步，则 fast 走了 2k 步，设环起点到相遇点的距离为 m，则环起点距头节点 k - m；相遇点到环起点的距离为 2k - k - m 步（k- m）
- 寻找链表的中点
- 快指针每次走两步
- 寻找链表的倒数第 k 个元素
- 让快指针先走 k 步
- 删除排列数组中的重复项（leedcode-26）
- 让快指针在前面探路，找到一个和满指针不同的元素时：nums[++slow] = nums[fast];
左右指针
- 二分查找
- 两数之和（leedcode-1）
- 问题描述：给定一个已按照升序排列的有序数组，找到两个数使得他们相加之和等于目标数，返回下标
- 只要数组有序，就应该想到使用双指针
- 接雨水（leedcode-42）
- 问题描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
思想：
- 将问题细化为每一个柱子接的最大雨水，求和：ans += Math.min(l_max[k], r_max[k]) - height[k];
- l_max：当前柱子左边的最高柱子（包括该柱子，避免出现负数）
- r_max：当前柱子右边的最高柱子（包括该柱子）
- 暴力求解
- 使用备忘录先记录下 [1…n-2] 的左右最大值
- 使用左右指针记录左右最大值（从两边开始，谁小谁移动）
- 滑动窗口