双指针不是某一种算法，而是一类算法，原则上使用两个变量作为指针操作数组、链表等的算法都可称为双指针。根据问题的不同，双指针采用不同的更新策略， 就形成了不同的模板。今天就来大概地总结一下这些模板。
前后双指针
“原地删除数组中特定元素”问题
例如 27.移除元素：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 ：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
我们可以使用双指针来原地修改：右指针指向当前将要处理的元素 （即判断它是否为“特定元素”，在本题中，“特定元素”是某个具体的值）， 左指针指向下一个将要赋值的位置，它的左侧是处理完的部分。不难想到右指针一定在左指针前面。
有两种思路来更新双指针：
一种是先更新左指针，再用循环更新右指针，使其跳过不满足要求的元素。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = 0, 0
while j <= len(nums) - 1:
while j <= len(nums) - 1 and nums[j] == val:
j += 1
if j <= len(nums) - 1:
nums[i] = nums[j]
i += 1
j += 1
return i
不难发现，第一种思路中指针的移动较为复杂，所以更推荐下面这种思路。 在外层循环更新右指针，每次移动一步，只要没碰到“特定元素”就都可以移动左指针。即先更新右指针，再更新左指针。因为右指针只通过外层循环前进， 思路要清晰的多。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
for j in range(len(nums)):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
数组换成链表也是同样的做法，只不过，链表不能用 for-in 枚举右指针，
需要 while 配合指针迭代前进。
# 203. 移除链表元素
# 给你一个链表的头节点 head 和一个整数 val ，
# 请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy = ListNode(next=head)
left, right = dummy, head
while right:
if right.val != val:
left.next = right
left = left.next
right = right.next
left.next = None
return dummy.next
类似的题目还有 26.删除有序数组中的重复项 与 80.删除有序数组中的重复项 II 等。以后者为例：
给你一个有序数组 nums，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 ：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。不需要考虑数组中超出新长度后面的元素。
它不过是对于“特定元素”的定义做了改变，我们可以还用上面的思路完成。 对于每个右指针所指元素，当且仅当左指针前面两个都已经是相同元素时需要删除。为了照顾边界，左右指针都从索引 2 出发。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 2
for j in range(2, len(nums)):
if nums[i - 2] != nums[j]:
nums[i] = nums[j]
i += 1
return i
partition 问题
partition 问题通常表述为“对一个数组原地排序，使得同一类别的元素排在相邻位置”。
例如 905.按奇偶排序数组。
# 给定一个非负整数数组 A，返回一个数组，在该数组中，
# A 的所有偶数元素之后跟着所有奇数元素。
# 你可以返回满足此条件的任何数组作为答案。
# 示例：
# 输入：[3,1,2,4]
# 输出：[2,4,3,1]
# 输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
i = 0
for j in range(0, len(nums)):
if nums[j] % 2 == 0:
nums[i], nums[j] = nums[j], nums[i]
i += 1
return nums
可以看到它的解答同“原地删除数组中特定元素”问题的解答十分相似。
左指针 i 标识数组左侧区域（偶数元素区）的下一个待填入位置，右指针 j 遍历数组，
把偶数交换到左侧。理解这种写法的关键在于注意到左指针的更新仅与右指针元素有关，
且 [i, j) 区间内全是奇数。特别的，因为左指针要么与右指针重合，要么指向奇数，
所以不可能把偶数交换到右侧去。
由此可以抽象出 partition 函数的模板。
def partition(nums: List[int], left: int, right: int, pred: Callable[[int], bool])-> int:
i = left
for j in range(left, right + 1):
if pred(j):
nums[i], nums[j] = nums[j], nums[i]
i += 1
return i
nums[left:right+1] 是要 partition 的区间，pred 是一个接收索引返回布尔值的函数，
令 pred 返回 True 的索引处的元素最终会聚集在区间的左侧，反之在右侧。
partition 函数最终返回分界面右端索引，即右侧区域起始索引。
我们可以用这个函数解决经典的“荷兰国旗问题”。
# 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，
# 使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
# 此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
# 示例 ：
# 输入：nums = [2,0,2,1,1,0]
# 输出：[0,0,1,1,2,2]
class Solution:
def sortColors(self, nums: List[int]) -> None:
def partition(nums: List[int], left: int, right: int, pred: Callable[[int], bool])-> int:
# ...
a = partition(nums, 0, len(nums) - 1, lambda j: nums[j] == 0)
partition(nums, a, len(nums) - 1, lambda j: nums[j] == 1)
三类数的 partition 可以分为两次两类数的 partition。
同理，K 类数的 partition 可以分为 K-1 次两类数的 partition。
partition 函数也是经典的快速排序的重要组成部分。
def quick_sort(array, left, right):
if left >= right:
return
def partition(nums: List[int], left: int, right: int, pred: Callable[[int], bool])-> int:
# ...
pivot = array[right]
mid = partition(array, left, right - 1, lambda j: array[j] <= pivot)
array[right], array[mid] = array[mid], array[right]
quick_sort(array, left, mid - 1)
quick_sort(array, mid + 1, right)
滑动窗口
滑动窗口的基本模板是这样的：
def slidingWindow(s):
ans = ...
left, right = 0, 0
window = ...
while right < len(s):
window.add(s[right])
right += 1
while window needs shrink:
update(ans)
window.remove(s[left])
left += 1
return ans
外层循环先把右指针元素添加进表示窗口的数据结构，再自增右指针；
内层循环则先把左指针元素移出窗口，再自增左指针。
先更新窗口、再更新指针的操作顺序不能颠倒，否则会出现越界错误。
更新答案的操作可以放在内层循环之中或之后，
取决于该处的左开右闭区间 [left, right) 是否符合题目要求。
例如 剑指 Offer II 008. 和大于等于 target 的最短子数组：
# 给定一个含有 n 个正整数的数组和一个正整数 target。
# 找出该数组中满足其和 ≥ target 的长度最小的连续子数组，
# 并返回其长度。如果不存在符合条件的子数组，返回 0。
#
# 示例 1：
# 输入：target = 7, nums = [2,3,1,2,4,3]
# 输出：2
# 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
#
# 示例 2：
# 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
# 输出：0
import sys
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
s = 0
ans = sys.maxsize
for right in range(len(nums)):
s += nums[right]
while s >= target:
ans = min(ans, right - left + 1)
s -= nums[left]
left += 1
return ans if ans != sys.maxsize else 0
这里“表示窗口的数据结构”实际上是 s，存放窗口子数组的元素和。
另外，外层循环使用 for 来枚举，等价于右指针自增操作被放到了循环的最后进行。因而内层循环之中或之后处的区间变成了 [left, right]，
此时左指针还有可能比右指针刚好大 1，用于表示空区间，
鉴于此，最好还是像模板中那样用两个 while 循环。
再看示例 剑指 Offer 48. 最长不含重复字符的子字符串
# 请从字符串中找出一个最长的不包含重复字符的子字符串，
# 计算该最长子字符串的长度。
# 示例 1:
# 输入: "abcabcbb"
# 输出: 3
# 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
# 示例 2:
# 输入: "bbbbb"
# 输出: 1
# 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left, right = 0, 0
ans = 0
window = {}
while right < len(s):
c = s[right]
if c not in window:
window[c] = 0
window[c] += 1
right += 1
while window[c] > 1:
window[s[left]] -= 1
left += 1
ans = max(ans, right - left)
return ans
哈希表 window 存放区间中字符的出现次数，区间收缩条件是区间最右端（即 right - 1 位置）元素出现过两次，自增左指针直到第一次出现的位置被跳过。这道题内层循环中的区间都不满足题意，
所以答案的更新放在内层循环之后。实际上，如果我们改用哈希表来存放每个字符上次出现的位置，
我们就可以让左指针一次性跳过上次出现的位置，但那就不是模板了，所以这里不做介绍。
更复杂的问题，如 76.最小覆盖子串，不过是增加了窗口维护的难度。
# 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
# 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
# 注意：
# 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
# 如果 s 中存在这样的子串，我们保证它是唯一的答案。
#
# 示例 ：
# 输入：s = "ADOBECODEBANC", t = "ABC"
# 输出："BANC"
class Solution:
def minWindow(self, s: str, t: str) -> str:
need, window = {}, {}
need_cnt = len(t)
for c in t:
if c not in need:
need[c] = 0
need[c] += 1
left = 0
ans = (0, sys.maxsize)
for right in range(len(s)):
if s[right] not in window:
window[s[right]] = 0
window[s[right]] += 1
if s[right] in need and window[s[right]] <= need[s[right]]:
need_cnt -= 1
while need_cnt == 0:
if right - left < ans[1] - ans[0]:
ans = (left, right)
if s[left] in need and window[s[left]] <= need[s[left]]:
need_cnt += 1
window[s[left]] -= 1
left += 1
return s[ans[0]:ans[1] + 1] if ans[1] != sys.maxsize else ""
这里的哈希表 window 仍然存放区间中各个字符的出现次数，
而哈希表 need 则存放需要的各个字符及需要的个数。
显然，当 need 为 window 的子集时，这个区间是符合题意的。
但是如果每次都比较两个哈希表的话，开销太大，因此引入一个变量 need_cnt 来标识 need 还缺少几个字符。因而，窗口更新的操作相对复杂了不少。
这一模板主要用来处理窗口大小可变的滑动窗口，事实上也能处理固定大小的窗口， 不过后者通常有更简单的写法。固定大小的滑动窗口例题可参考 567.字符串的排列，438.找到字符串中所有字母异位词 等。
推荐阅读：
如果你喜欢我的文章，请我吃根冰棒吧 (o゜▽゜)o ☆
最后附上 GitHub：https://github.com/gonearewe
