一、双指针的概念

1.1、什么是双指针？

顾名思议，双指针就是两个指针，但是该指针不同于 C，C++中的指针地址，而是一种记录两个索引的算法思想。

实际上，在很多简单题目中，我们经常使用单指针，比如我们通过索引来遍历某数组：

# 可以这样
for i in range(n):print(nums[i])
# 当然也可以这样
i = 0
while i<n:print(nums[i])i+=1
# 这样写为了引申出双指针，因为双指针一般用while来遍历

那么双指针实际上就是有两个这样的指针，最为经典的就是二分法中的左右双指针。

left, right = 0, len(nums)-1while left<right:if 一定条件:return 合适的值，一般是 l 和 r 的中点elif 一定条件:l+=1else:r-=1
# 因为 l == r，因此返回 l 和 r 都是一样的
return l

其实双指针是一个很宽泛的概念，就好像数组，链表一样，其类型会有很多很多， 比如二分法经常用到左右端点双指针。滑动窗口会用到快慢指针和固定间距指针。 因此双指针其实是一种综合性很强的类型，类似于数组，栈等。 但是我们这里所讲述的双指针，往往指的是某几种类型的双指针，而不是“只要有两个指针就是双指针了”。

有了这样一个算法框架，或者算法思维，有很大的好处。它能帮助你理清思路，当你碰到新的问题，在脑海里进行搜索的时候，双指针这个词就会在你脑海里闪过，闪过的同时你可以根据双指针的所有套路和这道题进行穷举匹配，这个思考解题过程本来就像是算法。

1.2、常见类型

指针一般情况下将分为三种类类型，分别是：

类型	特点
快慢指针	两个指针步长不同，一般情况下，快的走两步，慢的走一步
左右端点指针	两个指针分别指向头尾，并往中间移动，步长不确定，一般为1
区间指针	一般为滑动窗口，两个指针及其间距视作整体，窗口有定长有变长，每次操作窗口整体向右滑动

不管是哪一种双指针，只考虑双指针部分的话 ，由于最多还是会遍历整个数组一次，因此时间复杂度取决于步长，如果步长是 1，2 这种常数的话，那么时间复杂度就是 O(N)，如果步长是和数据规模有关（比如二分法），其时间复杂度就是 O(logN)。并且由于不管规模多大，我们都只需要最多两个指针，因此空间复杂度是 O(1)。下面我们就来看看双指针的常见套路有哪些。

1.2.1、快慢指针

本方法需要我们对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

具体的的示意图如下，同时也可以参考相似思路的，且比较简单的例题 141. 环形链表。

1.开始，乌龟slow在起始点，兔子fast在起点的下一个点。

2.乌龟走得慢每次走一步，兔子走得快，每次走两步。

继续走，兔子先进入环。

继续走，兔子一圈环快走完了，而乌龟刚进入环

最后乌龟走第一圈的时候，兔子第二圈刚好遇上。

注意：
当然具体第几圈遇上是不确定的，根据步长与环的大小相关，但是乌龟与兔子在圈中循环跑时，只要步长不一致，他们之间的最近距离会不断减少，总会相遇。

但是一般情况下会设置slow走一步，fast走两步，这个设定会产生很多有规律的数学推导，比如：142. 环形链表 II 中的快慢指针做法。

细节：

为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head（即与「乌龟」和「兔子」中的叙述相同）？

观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。

当然，我们也可以使用 do-while 循环或者其他方法。此时，我们就可以把快慢指针的初始值都置为 head。（所以，从这里可以得知，快慢指针初始化的值，可以相同也可以不同，具体取决于后面的判断条件）

复杂度分析：

时间复杂度：$O(N)$，其中 $N$ 是链表中的节点数。	空间复杂度：$O(1)$。
当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次；当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 $N$ 轮。	我们只使用了两个指针的额外空间。

题目类型：

	问题	例题
1	判断链表是否有环；寻找入环节点	141. 环形链表 | 142. 环形链表 II | 287. 寻找重复数
2	读写指针。将快指针的内容记录到慢指针的位置，典型的题目是原地删除(前置移动)重复元素。	26. 删除有序数组中的重复项 | 80. 删除有序数组中的重复项 II | 202. 快乐数

伪代码模板：

# 1.fast与slow初始化不同fast, slow = head, head.next
# 有环则一定相遇 退出循环后，后面return True
while fast!=slow :if not fast or not fast.next:return Falseslow=slow.nextfast=fast.next.next
return True# 2.fast与slow初始化相同
# fast = slow = head
fast = head
slow = head
while fast and fast.next:slow=slow.nextfast=fast.next.next# 有环则一定相遇 return Trueif slow == fast:return True
return False

1.2.2、左右端点指针

	问题	例题
1	二分查找	33. 搜索旋转排序数组 | 875. 爱吃香蕉的珂珂
2	有序数组暴力枚举。区别于上面的二分查找，这种算法指针移动是连续的，而不是跳跃性的	1. 两数之和 | 15. 三数之和 | 18. 四数之和 | 881. 救生艇
3	其他暴力枚举。比如：双边比较从大到小枚举，双边按条件枚举，无需排序或者已经有序（当然2和3其实可以归为一类）	977. 有序数组的平方 | 75. 颜色分类(Dutch National Flag Problem)

伪代码模板：

l = 0
r = n - 1
while l < r:if 找到了:return 找到的值if 一定条件1:l += 1else if  一定条件2:r -= 1
return 没找到

1.2.3、区间指针 - 滑动窗口

	区间指针	例题
1	定长滑动窗口	1456. 定长子串中元音的最大数目 | 剑指 Offer 22. 链表中倒数第k个节点
2	变长滑动窗口	713. 乘积小于 K 的子数组

伪代码模板：

l = 0
r = k
while 没有遍历完:自定义逻辑l += 1r += 1
return 合适的值

汇总

快慢指针	左右端点指针	区间指针-滑动窗口
判断链表是否有环；寻找入环节点	二分查找	定长滑动窗口
读写指针。将快指针的内容记录到慢指针的位置，典型的题目是原地删除(前置移动)重复元素。	有序数组暴力枚举。区别于上面的二分查找，这种算法指针移动是连续的，而不是跳跃性的	变长滑动窗口
	其他暴力枚举。比如：双边比较从大到小枚举，双边按条件枚举，无需排序或者已经有序（当然2和3其实可以归为一类）

二、经典例题

2.1、快慢指针

	问题	例题
1	判断链表是否有环；寻找入环节点	141. 环形链表 | 142. 环形链表 II | 287. 寻找重复数
2	读写指针。将快指针的内容记录到慢指针的位置，典型的题目是原地删除(前置移动)重复元素	26. 删除有序数组中的重复项 | 80. 删除有序数组中的重复项 II | 202. 快乐数

（1）、链表判环

141. 环形链表

141. 环形链表

解法1：哈希表
最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。

具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

注意：Python中的哈希表为字典和集合。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:seen = set()# 如果有环，虽然while死循环，但一定能在while中return Truewhile head:if head in seen:return Trueseen.add(head)head = head.next# 没有环则head的最后一个next会None而退出循环return False

解法2：快慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:slow = headfast = headwhile fast and fast.next:slow=slow.nextfast=fast.next.nextif fast==slow:return Truereturn False

142. 环形链表 II

142. 环形链表 II

解法1：哈希表
思路同上

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:seen = set()# 不允许修改表，用一个临时的指针来操作cur = headwhile cur:if cur in seen:return curseen.add(cur)cur=cur.nextreturn None

解法2：快慢指针
找数学规律：当快慢指针在环中相遇，链表的起点到入环点=快慢指针相遇点到入环点的距离。
所以相遇之后，定义新的游标在链表起点，此时该游标和慢指针一起以相同步长走，相遇即到了入环点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:slow = fast = headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextif fast==slow:cur = headwhile cur!=slow:cur=cur.nextslow=slow.nextreturn curreturn None

287. 寻找重复数

287. 寻找重复数
这题比较巧妙的一点是将nums的每个值当做下一个点的坐标，从而进行连接起来。我们来看看这个例子：
1 4 6 6 6 2 3
值为6时会指向索引6值为3的点，再以3为索引，又指向索引为3值为6的索引。

这道题同上一题 环形链表 II 的解法一致，重复元素即表示入环点

class Solution:def findDuplicate(self, nums: List[int]) -> int:fast = slow = nums[0]# 至少存在一个重复的数，说明不会死循环，一定存在slow==fast的情况# 不同判断是否有环，因为一定有while True:slow = nums[slow]fast = nums[nums[fast]]# 同环形链表的解法# 1. 先记录第一次相遇if slow == fast:# 记录一个起点与slow一同移动直到相遇，即为入环点cur = nums[0]while cur!=slow:cur = nums[cur]slow = nums[slow]return curreturn None

当然也有哈希表解法，同上，但时间复杂度高。

876. 链表的中间结点

慢指针走一步，快指针走两步，当快指针走到结尾，慢指针会走到链表中间。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextreturn slow

（2）、读写指针

26. 删除有序数组中的重复项 - 仅保留一次

26. 删除有序数组中的重复项
快指针用来判断重复，是否与前一个一样；慢指针用来存储非重复的值。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow = fast = 1while fast<len(nums):if nums[fast]!=nums[slow-1]:nums[slow]=nums[fast]slow+=1fast+=1return slow

80. 删除有序数组中的重复项 II - 保留两次重复

80. 删除有序数组中的重复项 II
这里保留重复的两次，题目解法同上。数组的前两个数必然可以被保留，因此，两个指针从2开始。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:slow = fast = 2while fast<len(nums):if nums[fast]!=nums[slow-2]:nums[slow] = nums[fast]slow+=1fast+=1return slow

递推：删除且保留k次重复

从前面两题我们可以总结出，如过要保留重复的k次：

class Solution:def removeDuplicates(self, nums: List[int], k: int) -> int:# 从第k个开始slow = fast = kwhile fast<len(nums):if nums[fast]!=nums[slow-k]:nums[slow] = nums[fast]slow+=1fast+=1return slow

202. 快乐数

202. 快乐数
通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针，但数据仍然形成链表结构。起始数字是链表的头 “节点”，链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。

意识到我们实际有个链表，那么这个问题就可以转换为检测一个链表是否有环。因此我们在这里可以使用弗洛伊德循环查找算法。这个算法是两个奔跑选手，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的慢的称为 “乌龟”，跑得快的称为 “兔子”。

不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。

class Solution:def isHappy(self, n: int) -> bool:def get_next(number):total_sum = 0while number>0:number, digit = divmod(number, 10)total_sum+=digit**2return total_sumslow = fast = n# fast!=1判断是否是快乐数# fast!=slow 说明有环，进行打破死循环# 快乐数的判断快于环的判断，所以会在打破循环前判断是否是快乐数while fast!=1:slow = get_next(slow)fast = get_next(get_next(fast))if fast==slow:breakreturn fast==1

2.2、左右端点指针

	问题	例题
1	二分查找	33. 搜索旋转排序数组 | 875. 爱吃香蕉的珂珂
2	有序数组暴力枚举。区别于上面的二分查找，这种算法指针移动是连续的，而不是跳跃性的	1. 两数之和 | 15. 三数之和 | 18. 四数之和 | 881. 救生艇
3	其他暴力枚举。比如：双边比较从大到小枚举，双边按条件枚举，无需排序或者已经有序（当然2和3其实可以归为一类）	977. 有序数组的平方 | 75. 颜色分类(Dutch National Flag Problem)

（1）、二分法

33. 搜索旋转排序数组

33. 搜索旋转排序数组

但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1],nums[r]]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

class Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)-1while l<=r:mid = (l+r)//2if nums[mid]==target:return midelse:# 以有序序列为分界线，进行两次二分，需要区分有顺序的两个部分# [4,5,6,7,0,1,2]# 说明在左半区 [4,5,6,7]if nums[0]<=nums[mid]:# 在该半区之中再去二分，以mid为中点# 在左半边[4]if nums[0]<=target<nums[mid]:r = mid - 1# 在右半边[5,6,7]else:l = mid + 1# [5,6,7,0,1,2,4]# 否则在右半区 [0,1,2,4]else:# [1,2,4]if nums[mid]<target<=nums[len(nums)-1]:l = mid+1# [0]else:r = mid-1return -1

875. 爱吃香蕉的珂珂

875. 爱吃香蕉的珂珂
这一题要注意一点，当sum_time==h时，不能直接return mid，因为比如：math.ceil(10/5)到math.ceil(10/9)这个5-9与10相除向上取整结果都为2，但是珂珂喜欢慢慢吃，也就是吃的尽量少一点，所以要取最小值5，所以，我们在sum_time==h时，试探性的将right=mid-1，而不是直接return mid。

最后退出循环后，l>=r，之所以会大，因为sum_time==h后的right=mid-1不成功，下一次循环l=mid+1而加回来，无法在变小了，所以最后返回return l 而不是 r。

import math
class Solution:def minEatingSpeed(self, piles: List[int], h: int) -> int:l, r = 1, max(piles)while l<=r:mid = (l+r)//2sum_time = sum([math.ceil(i/mid) for i in piles])if sum_time>h:l = mid+1elif sum_time<h:r = mid-1else:# 对于 [1,1,1,999999999] 和 10# 值在 142857143 和 二分得出的156250000中间结果都为10# 但是珂珂喜欢慢慢吃，也就是说数值得最小到刚好满足10h吃完# 所以当sum_time==h时，咱们还是要减少mid的值试试# 即便减少不成功，下一次sum_time>h时，l = mid+1也会加回来# 所以最后while结束后，应该返回leftr = mid-1return l

（2）、有序数组暴力枚举 - N数和问题

已知一组数组和一个目标值target，求不重复的在数组中取N个数的和为target的组合。

一般做这样的题的思路是用双指针，分别指向数组的左右两端，并且，数组需要排好序，从小到大。

因为排序后，左右指针才能有规律的移动，比如：当left+right的值大于target，说明他们两个太大了，需要减小，那么只能通过right左移来减小总体值（为什么不让left左移呢？因为不能重复取，之前取过了，就要移向新的值）；当left+right的值小于target，那么只能通过left右移来增加总体值。

当然，当left+right的值等于target，即为结果。

1. 两数之和

1. 两数之和
这题因为需要记录索引，所以将排序前，将值与原始索引绑定起来。

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:num_ind = []# 值与坐标进行绑定for ind, val in enumerate(nums):num_ind.append([val, ind])num_ind.sort(key=lambda x:x[0])# 开始双指针left, right = 0, len(nums)-1while left<right:# 三个条件，>target, <target, =targetif num_ind[left][0]+num_ind[right][0]>target:right-=1elif num_ind[left][0]+num_ind[right][0]<target:left+=1else:return [num_ind[left][1], num_ind[right][1]]return []

15. 三数之和

15. 三数之和

咱们利用上一题的函数两数之和，每次遍历第一个数，该第一个数的后面的数求两数之和，与第一个数相加为target则保存为结果。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res = []nums.sort()# 类似于两数之和def twoSum(start, target):res = []left, right = start, len(nums)-1while left<right:#（注意不是left>0）因为起始点不是0而是startif left>start and nums[left]==nums[left-1]:left+=1continueif right<len(nums)-1 and nums[right]==nums[right+1]:right-=1continueif nums[left]+nums[right]>target:right-=1elif nums[left]+nums[right]<target:left+=1else:res.append([nums[left],nums[right]])right-=1left+=1return res # 这里减去2，也就是至少保证剩下两个数在-1和-2。当然也可以不减for start in range(len(nums)-2):# 重复的需要去掉 [-1, -1, 0, 1] 这里前面两个-1都会取到后面的[0,1]if start>0 and nums[start]==nums[start-1]:continue# 这里除了left和right(去掉right，一定为len(nums)无需传入)# 第三个参数传入负的值，因为三数和为零# 在传入个起始坐标,twolist = twoSum(start+1, -nums[start])for twol in twolist:if sum(twol+[nums[start]])==0:res.append(twol+[nums[start]])return res

18. 四数之和

18. 四数之和
这题同样利用上前面两数之和与三数之和，层层嵌套，最内层还是两数之和。外面两层的三数之和与四数之和分别与两数之和相加，为target则return或者保存为最终的结果。

class Solution:def fourSum(self, nums: List[int], target: int) -> List[List[int]]:res = []nums.sort()# 相同的两数之和def twoSum(start, target):res = []left, right = start, len(nums)-1while left<right:if left>start and nums[left]==nums[left-1]:left+=1continueif right<len(nums)-1 and nums[right]==nums[right+1]:right-=1continueif nums[left]+nums[right]>target:right-=1elif nums[left]+nums[right]<target:left+=1else:res.append([nums[left],nums[right]])left+=1right-=1return res# 相同的三数之和def threeSum(start, target):res = []for sec in range(start, len(nums)):if sec>start and nums[sec]==nums[sec-1]:continuetwolist = twoSum(sec+1, target-nums[sec])for twol in twolist:if sum(twol+[nums[sec]])==target:res.append(twol+[nums[sec]])return res# 可以减3，也可以不减for start in range(len(nums)-3):if start>0 and nums[start]==nums[start-1]:continuethreelist = threeSum(start+1, target-nums[start])for threel in threelist:if sum(threel+[nums[start]])==target:res.append(threel+[nums[start]])return res

递推：N数之和

我们可以发现，除了最内层的两数之和这个函数，其他函数可以层层嵌套，写成递归形式，于是我们整理如下：

def nSum(nums, start, target, k):res = []# 大于两数之和的层层嵌套if k>2:for i in range(start, len(nums)):if i>start and nums[i]==nums[i-1]:continuenlist = nSum(nums, i+1, target-nums[i],k-1)for nl in nlist:if sum(nl+[nums[i]])==target:res.append(nl+[nums[i]])# 两数之和else:left, right = start, len(nums)-1while left<right:if left>start and nums[left]==nums[left-1]:left+=1continueif right<len(nums)-1 and nums[right]==nums[right+1]:right-=1continueif nums[left]+nums[right]>target:right-=1elif nums[left]+nums[right]<target:left+=1else:res.append([nums[left],nums[right]])right-=1left+=1return res# 四数之和
nums = [1,0,-1,0,-2,2] 
k = 4
target = 0
start = 0
# [[1, 2, -1, -2], [0, 2, 0, -2], [0, 1, 0, -1]]
# 三数之和
nums = [-1,0,1,2,-1,-4]
k = 3
nums.sort()
target = 0
start = 0
k = 3
# 函数入口
nSum(nums, start, target, k)

881. 救生艇

881. 救生艇

class Solution:def numRescueBoats(self, people: List[int], limit: int) -> int:people.sort()light,heavy = 0, len(people)-1count = 0while light<=heavy:if people[light]+people[heavy]<=limit:light+=1heavy-=1else:heavy-=1count+=1return count

（3）、其他暴力枚举

75. 颜色分类 - 类似于荷兰国旗问题

75. 颜色分类
两个左右指针分别用来存储0和2，遍历nums，找到0则与左指针交换，找到2则与右指针交换，注意相同值的交换[2,1,2]，所以需要判断交换后nums[i]是否还为原值，除此之外，需要防止越界，内部要加上判断条件 i<=p2。

class Solution:def sortColors(self, nums: List[int]) -> None:n = len(nums)p0, p2, i = 0, n-1, 0while i<=p2:# 防止 [2,1,2],if改为while# 防止 [2,2,2],p2一直-1小于0越界，加上while i<=p2while i<=p2 and nums[i]==2:nums[i], nums[p2] = nums[p2], nums[i]p2-=1if nums[i]==0:nums[i], nums[p0] = nums[p0], nums[i]p0+=1i+=1return nums

977. 有序数组的平方

977. 有序数组的平方
两端的平方为最大值，每次将最大值放入一个新生成的list的从右到左放置。

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:n = len(nums)ans = [0]*nleft,right,pos = 0, n-1,n-1while left<=right:if nums[left]**2>nums[right]**2:ans[pos]=nums[left]**2left+=1else:ans[pos]=nums[right]**2right-=1pos-=1return ans

2.3、区间指针 - 滑动窗口

	固定间距指针	例题
1	定长滑动窗口	1456. 定长子串中元音的最大数目 | 剑指 Offer 22. 链表中倒数第k个节点
2	变长滑动窗口	713. 乘积小于 K 的子数组

（1）、定长滑动窗口

1456. 定长子串中元音的最大数目

1456. 定长子串中元音的最大数目

先求出从起点开始定长窗口，每次移动，去掉首部，加上尾部。

class Solution:def maxVowels(self, s: str, k: int) -> int:def isVowel(ch):return int(ch in 'aeiou')count = 0for i in range(k):if isVowel(s[i]):count+=1ans = countfor i in range(k, len(s)):count = count-isVowel(s[i-k])+isVowel(s[i])ans = max(ans, count)return ans

剑指 Offer 22. 链表中倒数第k个节点

剑指 Offer 22. 链表中倒数第k个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:left = right = headwhile k:right=right.nextk-=1while right:left=left.nextright=right.nextreturn left

（2）、变长滑动窗口

713. 乘积小于 K 的子数组

713. 乘积小于 K 的子数组
本题采用的是双指针滑动窗口，大循环是右指针的移动，内部小循环是左指针的移动。

class Solution:def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:left = right =0# 记录组合个数ans = 0# 记录乘积mul = 1while right<len(nums):mul*=nums[right]# 防止left一直+而越界，需要left<=rightwhile mul>=k and left<=right:mul/=nums[left]left+=1#每次右指针位移到一个新位置，应该加上 x 种数组组合：#  nums[right]#  nums[right-1], nums[right]#  nums[right-2], nums[right-1], nums[right]#  nums[left], ......, nums[right-2], nums[right-1], nums[right]ans+=right-left+1right+=1return ans

参考

官方解题 环形链表
快慢指针
官方解题 搜索旋转排序数组
713.官方思路秒懂○注释详细○双指针滑窗 【附通用滑窗模板】