【双指针法】:这么常用的你怎么能不知道

memRD8 · 2025-4-13 09:48:15

前言

一文带你回顾双指针法的各种应用。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！
双指针法介绍

在很多的场景中我们经常能够遇到使用双指针法的题型，用了这么多的双指针法，所以本文给大家总结下双指针法的各种使用场景。
首先我们来回顾下双指针法的思想，什么是双指针法？以及其作用？

通过维护两个指针来遍历或操作数据，以达到高效解决问题的目的。
双指针法通常可以优化时间复杂度，将嵌套循环的问题转化为单层循环问题。

具体的实现过程就是设定快慢指针。根据题目的场景要求来设定快慢指针具体的实现功能。其运行过程如下：

双指针法实战篇

数组篇

移除元素

27. 移除元素 - 力扣（LeetCode）

相关技巧：首先定义快慢指针：快指针：用来寻找值不为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移动零

283. 移动零 - 力扣（LeetCode）

相关技巧：同样的思路来做就行了，定义快慢指针：快指针：向后遍历数组中的元素如果不是零就与慢指针交换。慢指针：用来与快指针的不为零元素进行交换。当快指针遍历完后，慢指针之前的所有元素即不为零。
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有序数组的平方

977. 有序数组的平方 - 力扣（LeetCode）

相关技巧：注意看这道题，与我们之前遇到的不太一样。分析题意，平方后按升序排序，其平方前有正负之分。唯一我们需要判别的就是平方后哪个更大的问题。同时我们可以发现，最大的元素一定是在两端产生的，所以我们这里的双指针走向是从两端向中间移动。然后进行比较，两端的哪个大放在排序后的最后一个，然后在比较哪个大放在前一个，直到遍历完成。
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链表篇

反转链表

206. 反转链表 - 力扣（LeetCode）

相关技巧：其实这道题的思路还是比较简单的，我们直接使用双指针法来做，初始状态，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 = nextclass 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环形链表

142. 环形链表 II - 力扣（LeetCode）

相关技巧：用双指针找环的问题是很经典的。我们设置快慢指针，其从同个地方出发，然后两者以不同的速度往下遍历，如果存在环，那么其一定会在环形中的某个节点相遇，如果没有环，那么绝对不会相遇。
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass 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字符串篇

反转字符串

344. 反转字符串 - 力扣（LeetCode）

相关技巧：相信做到做到现在，做了这么多双指针法的题目，这种应该能够一眼看出怎么做了，定义双指针从两端一同向中间遍历交换即可。
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替换数字

54. 替换数字（第八期模拟笔试）

相关技巧：替换数字成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 <= '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 = s[j]          else:             s_list = '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数之和篇

三数之和

15. 三数之和 - 力扣（LeetCode）

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]:       result = []       nums.sort()             for i in range(len(nums)):          # 如果第一个元素已经大于0，不需要进一步检查          if nums > 0:             return result                      # 跳过相同的元素以避免重复          if i > 0 and nums == nums[i - 1]:             continue                         left = i + 1          right = len(nums) - 1                      while right > left:             sum_ = nums + nums[left] + nums[right]                               if sum_ < 0:                   left += 1             elif sum_ > 0:                   right -= 1             else:                   result.append([nums, 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四数之和

18. 四数之和 - 力扣（LeetCode）

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 > target and nums > 0 and target > 0:# 剪枝（可省）             break          if i > 0 and nums == nums[i-1]:# 去重             continue          for j in range(i+1, n):             if nums + 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 + nums[j] + nums[left] + nums[right]                   if s == target:                      result.append([nums, 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】:带你一步步从原理到构建
 【栈与队列】：基础实战篇