最近系统学习了部分双指针算法的技巧，在此系统总结一下。
一，引言
双指针部分的题目非常多，灵活性比较高，总结一些非常有意义。同时一篇博客显然难以囊括所有题型，本次总结主要聚焦相向指针与同向指针，后续将有更多的指针总结。
二，相向指针
2.1反转字符串与回文字符串–同步相向指针
反转字符串与回文字符串是较为简单与理解的相向指针用法，核心思想即为一者指头，一者指尾，同步相向移动，边移动边判断即可。
例2.1.1反转字符数组
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
代码如下，可以看到非常简单，设置一个头指针一个尾指针即可。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
head=0
tail=len(s)-1
while head<tail:
s[head],s[tail]=s[tail],s[head]
head+=1
tail-=1
例2.1.2垂直翻转子矩阵
给你一个 m x n 的整数矩阵 grid，以及三个整数 x、y 和 k。
整数 x 和 y 表示一个 正方形子矩阵 的左上角下标，整数 k 表示该正方形子矩阵的边长。
你的任务是垂直翻转子矩阵的行顺序。
返回更新后的矩阵。
示例 1：
输入： grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], x = 1, y = 0, k = 3
输出： [[1,2,3,4],[13,14,15,8],[9,10,11,12],[5,6,7,16]]
此题其实与反转字符串没什么区别，只是将头尾指针换成了上下指针逐一交换行元素即可。同时涉及到批量交换元素，可以直接使用python列表里的切片赋值来进行批量反转，这样可以使得代码非常简洁且易懂。
class Solution:
def reverseSubmatrix(self, grid: List[List[int]], x: int, y: int, k: int) -> List[List[int]]:
head=x
tail=x+k-1
while head<tail:
grid[head][y:y+k],grid[tail][y:y+k]=grid[tail][y:y+k],grid[head][y:y+k]
head+=1
tail-=1
return grid
例2.1.3反转字符串中元音字母
给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现不止一次。
示例 1：
输入：s = “IceCreAm”
输出：“AceCreIm”
解释：
s 中的元音是 ['I', 'e', 'e', 'A']。反转这些元音，s 变为 “AceCreIm”.
注意，在python，java中字符串属于不可变量，不可以直接像数组一样首尾交换，需要先转换为数组然后再进行操作。
写法一：循环嵌套
class Solution:
def reverseVowels(self, s: str) -> str:
head=0
tail=len(s)-1
temp=list(s)
while head<tail:
while head<len(s) and temp[head] not in 'aeiouAEIOU':
head+=1
while tail>=0 and s[tail] not in 'aeiouAEIOU':
tail-=1
if head>=tail:
break
temp[head],temp[tail]=temp[tail],temp[head]
head+=1
tail-=1
return "".join(temp)写法二：if-else判断
class Solution:
def reverseVowels(self, s: str) -> str:
head=0
tail=len(s)-1
temp=list(s)
while head<tail:
if s[head] not in 'aeiouAEIOU':
head+=1
elif s[tail] not in 'aeiouAEIOU':
tail-=1
else:
temp[head],temp[tail]=temp[tail],temp[head]
head+=1
tail-=1
return "".join(temp)
上述两种写法都比较直观，性能也几乎一直，第二种写法比第一种稍微慢一点，个人比较推荐第二种，因为不需要像第一种那样加三个条件避免指针走过头。
例2.1.3验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
这题需要有一个前置处理，先利用快慢指针将含有非字母数字字符的字符串转换为纯数字字母串（后面同向指针里会讲到）
class Solution:
def isPalindrome(self, s: str) -> bool:
res=""
fast=0
while fast<len(s):
if s[fast].isalnum():
res+=s[fast].lower()
fast+=1
head,tail=0,len(res)-1
while head<tail:
if res[head]!=res[tail]:
return False
head+=1
tail-=1
return True然而，这样写，首先空间复杂度会变成O（n）,时间复杂度还会变成O(2*N)，这是效率比较低的做法，如果使用if_else来代替第一重循环，则会变得非常简洁且快速。
class Solution:
def isPalindrome(self, s: str) -> bool:
head,tail=0,len(s)-1
while head<tail:
if not s[head].isalnum():
head+=1
elif not s[tail].isalnum():
tail-=1
else:
if s[head].lower()!=s[tail].lower():
return False
head+=1
tail-=1
return True例2.1.4给植物浇水Ⅱ
lice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n – 1 。其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
- Alice 按 从左到右 的顺序给植物浇水，从植物
0开始。Bob 按 从右到左 的顺序给植物浇水，从植物n - 1开始。他们 同时 给植物浇水。 - 无论需要多少水，为每株植物浇水所需的时间都是相同的。
- 如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先（立即）重新装满罐子，然后给植物浇水。
- 如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
示例 1：
输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5 输出：1 解释： - 最初，Alice 和 Bob 的水罐中各有 5 单元水。 - Alice 给植物 0 浇水，Bob 给植物 3 浇水。 - Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。 - Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。 所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。
这道题目本质上是回文串的思路，其为首尾指针的同步浇水。注意，是同步浇水，A浇水一次，B就必须浇水一次。本质上与回文串的判别并无区别。
class Solution:
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
head,tail=0,len(plants)-1
water_a=capacityA
water_b=capacityB
res=0
while head<tail:
if water_a<plants[head]:
res+=1
water_a=capacityA
water_a-=plants[head]
head+=1
if water_b<plants[tail]:
res+=1
water_b=capacityB
water_b-=plants[tail]
tail-=1
return res+1 if max(water_b,water_a)<plants[head] else res2.2异步相向指针
所谓异步相向指针即是在相向扫描过程中，head与tail因为一些条件会出现不同程度的异步。比如选取两个之中的一个作为结果，一个移动一个不动。也有左右异步移动以求得一个中间区间。
例2.2.1有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
选取首尾更大的一个值作为新数组的值加入，最后翻转即可。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
head,tail=0,len(nums)-1
res=[]
while head<=tail:
a=pow(nums[head],2)
b=pow(nums[tail],2)
if a>=b:
res.append(a)
head+=1
else:
res.append(b)
tail-=1
return res[::-1]例2.2.2找到K个最接近的元素
给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
- |a – x| < |b – x| 或者
- |a – x| == |b – x| 且 a < b
示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3 输出：[1,2,3,4]
示例 2：
输入：arr = [1,1,2,3,4,5], k = 4, x = -1 输出：[1,1,2,3]
本题就是典型地通过异步相向指针求中间区间。当然，也有非常取巧的方法，一行代码即可解题。
方法一：绝对值排序
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
return sorted(sorted(arr,key=lambda num: abs(num-x))[:k])方法二：异步相向指针求中间区间
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
head,tail=0,len(arr)-1
while tail-head+1>k:
if abs(arr[head]-x)>abs(arr[tail]-x):
head+=1
else:
tail-=1
return arr[head:tail+1]两种方法都比较简洁，笔者推荐全部掌握。
例2.2.3数组种的k个最强值
给你一个整数数组 arr 和一个整数 k 。
设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：
- |arr[i] – m| > |arr[j] – m|
- |arr[i] – m| == |arr[j] – m|，且 arr[i] > arr[j]
请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。
中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于 ((n - 1) / 2) 的元素。
- 例如
arr = [6, -3,7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 – 1) / 2) = 2 ，中位数 arr[m] 的值为6。 - 例如
arr = [-7, 22,17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 – 1) / 2) = 1 ，中位数 arr[m] 的值为3。
示例 1：
输入：arr = [1,2,3,4,5], k = 2 输出：[5,1] 解释：中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。 注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 > 1 。
本题其实就是上一题的反面，直接照抄上一题代码然后翻转一下就行了
class Solution:
def getStrongest(self, arr: List[int], k: int) -> List[int]:
length=len(arr)-k
arr=sorted(arr)
x=arr[(len(arr)-1)//2]
head,tail=0,len(arr)-1
while tail-head+1>length:
if abs(arr[head]-x)>abs(arr[tail]-x):
head+=1
else:
tail-=1
return arr[:head]+arr[tail+1:]
例2.2.4两数之和Ⅱ
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
本题即是使用异步指针搜索一个元组。因为数组是有序的，所以可以用异步指针搜索和。
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left,right=0,len(numbers)-1
while left<right:
cur_sum=numbers[left]+numbers[right]
if cur_sum>target:
right-=1
elif cur_sum<target:
left+=1
else:
return [left+1,right+1]
return []
