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

目录

• 前言
  
• 双指针法介绍
  
• 双指针法实战篇
  
  
  
  • 数组篇
    
    
    
    • 移除元素
      
    • 删除有序数组中的重复项
      
    • 移动零
      
    • 有序数组的平方
      
    
    
  • 链表篇
    
    
    
    • 反转链表
      
    • 环形链表
      
    
    
  • 字符串篇
    
    
    
    • 反转字符串
      
    • 替换数字
      
    
    
  • N数之和篇
    
    
    
    • 三数之和
      
    • 四数之和
      
    
    
  
  
• 算法基础系列
  

前言

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

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

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

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

双指针法实战篇

数组篇

移除元素

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

相关技巧：首先定义快慢指针：快指针：用来寻找值不为val的元素。慢指针：用来更新新数组的下标
其含义一定要理解。具体什么意思：fast一直在数组循环，当找到值不为val的元素，就与slow交换，当fast遍历完整个数组，那么slow所代表的数组以内就都会是符合要求的值了。

1. class Solution:
2.     def removeElement(self, nums: List[int], val: int) -> int:
3.         # 快慢指针
4.         fast = 0  # 快指针
5.         slow = 0  # 慢指针
6.         size = len(nums)
7.         while fast < size:  # 不加等于是因为，a = size 时，nums[a] 会越界
8.             # slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
9.             if nums[fast] != val:
10.                 nums[slow] = nums[fast]
11.                 slow += 1
12.             fast += 1
13.         return slow

复制代码

删除有序数组中的重复项

26. 删除有序数组中的重复项 - 力扣（LeetCode）

相关技巧：相信大家如果认真的解过移除元素的题目，那么这题将十分简单。同样的定义快慢指针：快指针：向后遍历数组中的元素如果与当前元素重复即继续遍历。慢指针：用来更新数组使得到慢指针指向的位置无重复元素。

1. class Solution:
2.     def removeDuplicates(self, nums: List[int]) -> int:
3.         slow,fast=0,1
4.         while fast<len(nums):
5.             if nums[slow]!=nums[fast]:
6.                 nums[slow+1]=nums[fast]
7.                 slow=slow+1
8.             fast+=1
9.         return slow+1

复制代码

字符串篇

反转字符串

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

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

1. class Solution:
2.     def moveZeroes(self, nums: List[int]) -> None:
3.         """
4.         Do not return anything, modify nums in-place instead.
5.         """
6.         start,end=0,0
8.         while end<len(nums):
9.             if nums[end]!=0:
10.                 nums[start],nums[end]=nums[end],nums[start]
11.                 start+=1
12.             end+=1

复制代码

替换数字

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

相关技巧：替换数字成number，这里我们看如果我们正常的去做就是使用额外的空间，从原数组开始遍历，字母直接进入，数字变成number。那么我们能不能原地操作呢？双指针法就可帮你实现。但是有个细节，我们快慢指针的初始位置，快指针在扩充后的数组的末尾，慢指针在数组原来的最后一个元素上，然后慢指针向前遍历，快指针跟着向前，慢指针的字母直接到快指针位置，数字变成number在放在快指针位置，示意图如下：

1. class Solution:
2.     def sortedSquares(self, nums: List[int]) -> List[int]:
3.         left,right,n=0,len(nums)-1,len(nums)
4.         sorted=[0]*n
5.         while left<=right:
6.             if pow(nums[left],2)<=pow(nums[right],2):
7.                 sorted[n-1]=pow(nums[right],2)
8.                 right-=1
9.             else:
10.                 sorted[n-1]=pow(nums[left],2)
11.                 left+=1
12.             n-=1
13.         return sorted

复制代码

四数之和

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

1. # Definition for singly-linked list.
2. # class ListNode:
3. #     def __init__(self, val=0, next=None):
4. #         self.val = val
5. #         self.next = next
6. class Solution:
7.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
8.         pre,cur=None,head
9.         while cur:
10.             tmp=cur.next
11.             cur.next=pre
12.             pre=cur
13.             cur=tmp
14.         return pre

复制代码

算法基础系列

一文了解什么是数组及其经典考察题目
走进链表及其经典考察题目
还不知道什么是哈希表，看这篇文章就够了
字符串匹配究极大招【KMP】:带你一步步从原理到构建
【栈与队列】：基础实战篇

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！