前言
一文带你回顾双指针法的各种应用。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于 代码随想录 同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！
双指针法介绍
在很多的场景中我们经常能够遇到使用双指针法的题型，用了这么多的双指针法，所以本文给大家总结下双指针法的各种使用场景。
首先我们来回顾下双指针法的思想，什么是双指针法？以及其作用？
-
通过维护两个指针来遍历或操作数据，以达到高效解决问题的目的。
-
双指针法通常可以优化时间复杂度，将嵌套循环的问题转化为单层循环问题。
具体的实现过程就是设定快慢指针。根据题目的场景要求来设定快慢指针具体的实现功能。其运行过程如下：
双指针法实战篇
数组篇
移除元素
相关技巧：首先定义快慢指针：快指针：用来寻找值不为val的元素。慢指针：用来更新新数组的下标
其含义一定要理解。具体什么意思：fast一直在数组循环，当找到值不为val的元素，就与slow交换，当fast遍历完整个数组，那么slow所代表的数组以内就都会是符合要求的值了。
class Solution: def removeElement(self, nums: List[int], val: int) -> int: # 快慢指针 fast = 0 # 快指针 slow = 0 # 慢指针 size = len(nums) while fast < size: # 不加等于是因为，a = size 时，nums[a] 会越界 # slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换 if nums[fast] != val: nums[slow] = nums[fast] slow += 1 fast += 1 return slow 删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣（LeetCode）
相关技巧：相信大家如果认真的解过移除元素的题目，那么这题将十分简单。同样的定义快慢指针：快指针：向后遍历数组中的元素如果与当前元素重复即继续遍历。慢指针：用来更新数组使得到慢指针指向的位置无重复元素。
class Solution: def removeDuplicates(self, nums: List[int]) -> int: slow,fast=0,1 while fast<len(nums): if nums[slow]!=nums[fast]: nums[slow+1]=nums[fast] slow=slow+1 fast+=1 return slow+1 移动零
相关技巧：同样的思路来做就行了，定义快慢指针：快指针：向后遍历数组中的元素如果不是零就与慢指针交换。慢指针：用来与快指针的不为零元素进行交换。当快指针遍历完后，慢指针之前的所有元素即不为零。
class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ start,end=0,0 while end<len(nums): if nums[end]!=0: nums[start],nums[end]=nums[end],nums[start] start+=1 end+=1 有序数组的平方
相关技巧：注意看这道题，与我们之前遇到的不太一样。分析题意，平方后按升序排序，其平方前有正负之分。唯一我们需要判别的就是平方后哪个更大的问题。同时我们可以发现，最大的元素一定是在两端产生的，所以我们这里的双指针走向是从两端向中间移动。然后进行比较，两端的哪个大放在排序后的最后一个，然后在比较哪个大放在前一个，直到遍历完成。
class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: left,right,n=0,len(nums)-1,len(nums) sorted=[0]*n while left<=right: if pow(nums[left],2)<=pow(nums[right],2): sorted[n-1]=pow(nums[right],2) right-=1 else: sorted[n-1]=pow(nums[left],2) left+=1 n-=1 return sorted 链表篇
反转链表
相关技巧：其实这道题的思路还是比较简单的，我们直接使用双指针法来做，初始状态，pre为None，cur指向第一个节点，然后令cur每次指向pre，在两个同时向下移动一位，但这里需要注意下，我们改变cur指针指向后，cur就不再指向原本的下一位了，所以这里我们用个tmp来临时存储cur的下个节点，如此循环，即可完成反转链表功能。
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: pre,cur=None,head while cur: tmp=cur.next cur.next=pre pre=cur cur=tmp return pre 环形链表
相关技巧：用双指针找环的问题是很经典的。我们设置快慢指针，其从同个地方出发，然后两者以不同的速度往下遍历，如果存在环，那么其一定会在环形中的某个节点相遇，如果没有环，那么绝对不会相遇。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # If there is a cycle, the slow and fast pointers will eventually meet if slow == fast: # Move one of the pointers back to the start of the list slow = head while slow != fast: slow = slow.next fast = fast.next return slow # If there is no cycle, return None return None 字符串篇
反转字符串
相关技巧：相信做到做到现在，做了这么多双指针法的题目，这种应该能够一眼看出怎么做了，定义双指针从两端一同向中间遍历交换即可。
class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ left, right = 0, len(s) - 1 # 该方法已经不需要判断奇偶数，经测试后时间空间复杂度比用 for i in range(len(s)//2)更低 # 因为while每次循环需要进行条件判断，而range函数不需要，直接生成数字，因此时间复杂度更低。推荐使用range while left < right: s[left], s[right] = s[right], s[left] left += 1 right -= 1 替换数字
相关技巧：替换数字成number，这里我们看如果我们正常的去做就是使用额外的空间，从原数组开始遍历，字母直接进入，数字变成number。那么我们能不能原地操作呢？双指针法就可帮你实现。但是有个细节，我们快慢指针的初始位置，快指针在扩充后的数组的末尾，慢指针在数组原来的最后一个元素上，然后慢指针向前遍历，快指针跟着向前，慢指针的字母直接到快指针位置，数字变成number在放在快指针位置，示意图如下：
def main(): while True: try: s = input() # Python中使用input()获取输入 except EOFError: # 捕获EOFError异常，以处理输入结束的情况 break count = 0 # 统计数字的个数 s_old_size = len(s) for i in range(s_old_size): if '0' <= s[i] <= '9': count += 1 # 扩充字符串s的大小，也就是每个数字替换成"number"之后的大小 s_list = list(s) + [''] * (count * 5) s_new_size = len(s_list) # 从后向前将数字替换为"number" for i in range(s_new_size - 1, s_old_size - 1, -1): j = i - (s_new_size - s_old_size) if not ('0' <= s[j] <= '9'): s_list[i] = s[j] else: s_list[i] = 'r' s_list[i - 1] = 'e' s_list[i - 2] = 'b' s_list[i - 3] = 'm' s_list[i - 4] = 'u' s_list[i - 5] = 'n' i -= 5 print(''.join(s_list)) # 输出结果 if __name__ == "__main__": main() N数之和篇
三数之和
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: result = [] nums.sort() for i in range(len(nums)): # 如果第一个元素已经大于0，不需要进一步检查 if nums[i] > 0: return result # 跳过相同的元素以避免重复 if i > 0 and nums[i] == nums[i - 1]: continue left = i + 1 right = len(nums) - 1 while right > left: sum_ = nums[i] + nums[left] + nums[right] if sum_ < 0: left += 1 elif sum_ > 0: right -= 1 else: result.append([nums[i], nums[left], nums[right]]) # 跳过相同的元素以避免重复 while right > left and nums[right] == nums[right - 1]: right -= 1 while right > left and nums[left] == nums[left + 1]: left += 1 right -= 1 left += 1 return result 四数之和
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: nums.sort() n = len(nums) result = [] for i in range(n): if nums[i] > target and nums[i] > 0 and target > 0:# 剪枝（可省） break if i > 0 and nums[i] == nums[i-1]:# 去重 continue for j in range(i+1, n): if nums[i] + nums[j] > target and target > 0: #剪枝（可省） break if j > i+1 and nums[j] == nums[j-1]: # 去重 continue left, right = j+1, n-1 while left < right: s = nums[i] + nums[j] + nums[left] + nums[right] if s == target: result.append([nums[i], nums[j], nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1 elif s < target: left += 1 else: right -= 1 return result 算法基础系列
一文了解什么是数组及其经典考察题目
走进链表及其经典考察题目
还不知道什么是哈希表，看这篇文章就够了
字符串匹配究极大招【KMP】:带你一步步从原理到构建
【栈与队列】：基础实战篇
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
