https://labuladong.gitee.io/algo/1/5/
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针 和 快慢指针 。
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
数组问题中比较常见的快慢指针技巧，是让你原地修改数组，这里只强调滑动窗口算法的快慢指针特性，其他文章还有通过扩大和缩小「窗口」来解决某些问题
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
函数签名如下：
function removeDuplicates(nums: number[]): number {
};如果不是原地修改的话，我们直接 new 一个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。
但是现在题目让你原地删除，由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难。但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)。
我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
这样，就保证了 nums[0..slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0..slow] 就是整个数组去重之后的结果。
算法执行的过程如下 GIF 图：
function removeDuplicates(nums: number[]): number {
if (!Array.isArray(nums) || !nums.length) { return 0 }
let slow = 0
let fast = 0
while (fast < nums.length) {
if (nums[fast] !== nums[slow]) {
slow++
nums[slow] = nums[fast]
}
fast++
}
return slow + 1
};https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
和数组去重是一模一样的，唯一的区别是把数组赋值操作变成操作指针而已
算法执行的过程请看下面这个 GIF：
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function deleteDuplicates(head: ListNode | null): ListNode | null {
if (!head) { return head }
let slow = head
let fast = head
while (fast) {
if (slow.val !== fast.val) {
slow.next = fast
slow = fast
}
fast = fast.next
}
// 断开与后面重复元素的连接
slow.next = null;
return head
};https://leetcode.cn/problems/remove-element/
题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。
注意这里和有序数组去重的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++，这样可以保证 nums[0..slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。
function removeElement(nums: number[], val: number): number {
if (!Array.isArray(nums) || !nums.length) { return 0 }
let slow = 0
let fast = 0
while (fast < nums.length) {
if (nums[fast] !== val) {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
};https://leetcode.cn/problems/move-zeroes/
给你输入一个数组 nums，请你原地修改，将数组中的所有值为 0 的元素移到数组末尾，函数签名如下：
/**
Do not return anything, modify nums in-place instead.
*/
function moveZeroes(nums: number[]): void {
};题目让我们将所有 0 移到最后，其实就相当于移除 nums 中的所有 0，然后再把后面的元素都赋值为 0 即可。
所以我们可以复用上一题的 removeElement 函数
/**
Do not return anything, modify nums in-place instead.
*/
function moveZeroes(nums: number[]): void {
let p = removeElement(nums, 0)
for (;p < nums.length; p++) {
nums[p] = 0
}
};
function removeElement(nums: number[], val: number): number {
if (!Array.isArray(nums) || !nums.length) { return 0 }
let slow = 0
let fast = 0
while (fast < nums.length) {
if (nums[fast] !== val) {
nums[slow] = nums[fast]
slow++
}
fast++
}
return slow
};力扣第 167 题「两数之和 II」
https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/
只要数组有序，就应该想到双指针技巧
function twoSum(numbers: number[], target: number): number[] {
// 一左一右两个指针相向而行
let left = 0
let right = numbers.length - 1
while (left < right) {
const sum = numbers[left] + numbers[right]
if (sum == target) {
// 题目要求的索引是从 1 开始的
return [left + 1, right + 1]
} else if (sum < target) {
left++ // 让 sum 大一点
} else if (sum > target) {
right-- // 让 sum 小一点
}
}
return [-1, -1]
};力扣第 344 题「反转字符串」
https://leetcode.cn/problems/reverse-string/
/**
Do not return anything, modify s in-place instead.
*/
function reverseString(s: string[]): void {
let left = 0
let right = s.length - 1
while (left < right) {
let temp = s[left]
s[left] = s[right]
s[right] = temp
left++
right--
}
};力扣第 5 题「最长回文子串」
https://leetcode.cn/problems/longest-palindromic-substring/
函数签名如下：
function longestPalindrome(s: string): string {
};找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。
如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。所以我们可以先实现这样一个函数： 如果输入相同的 l 和 r，就相当于寻找长度为奇数的回文串，如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串。
function palindrome(s: string, l: number, r: number): string {
// 防止索引越界
while (l >= 0 && r < s.length() && s.charAt(l) === s.charAt(r)) {
// 双指针，向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}那么回到最长回文串的问题，解法的大致思路就是：
for 0 <= i < len(s): 找到以 s[i] 为中心的回文串 找到以 s[i] 和 s[i+1] 为中心的回文串 更新答案
最长回文子串使用的左右指针和之前题目的左右指针有一些不同：之前的左右指针都是从两端向中间相向而行，而回文子串问题则是让左右指针从中心向两端扩展。不过这种情况也就回文串这类问题会遇到，所以我也把它归为左右指针了。
function longestPalindrome(s: string): string {
let res: string = ''
for (let i = 0; i < s.length; i++) {
// 以 s[i] 为中心的最长回文子串
const s1 = palindrome(s, i, i)
const s2 = palindrome(s, i, i + 1)
const next = s1.length >= s2.length ? s1 : s2
if (next.length > res.length) {
res = next
}
}
return res
};
function palindrome(s: string, l: number, r: number): string {
// 防止索引越界
while (l >= 0 && r < s.length && s.charAt(l) === s.charAt(r)) {
// 双指针，向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
return s.substring(l + 1, r);
}