【双指针法】:这么常用的你怎么能不知道
目录[*]前言
[*]双指针法介绍
[*]双指针法实战篇
[*]数组篇
[*]移除元素
[*]删除有序数组中的重复项
[*]移动零
[*]有序数组的平方
[*]链表篇
[*]反转链表
[*]环形链表
[*]字符串篇
[*]反转字符串
[*]替换数字
[*]N数之和篇
[*]三数之和
[*]四数之和
[*]算法基础系列
前言
一文带你回顾双指针法的各种应用。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于 代码随想录 同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！
双指针法介绍
在很多的场景中我们经常能够遇到使用双指针法的题型，用了这么多的双指针法，所以本文给大家总结下双指针法的各种使用场景。
首先我们来回顾下双指针法的思想，什么是双指针法？以及其作用？
[*]通过维护两个指针来遍历或操作数据，以达到高效解决问题的目的。
[*]双指针法通常可以优化时间复杂度，将嵌套循环的问题转化为单层循环问题。
具体的实现过程就是设定快慢指针。根据题目的场景要求来设定快慢指针具体的实现功能。其运行过程如下：
双指针法实战篇
数组篇
移除元素
27. 移除元素 - 力扣（LeetCode）
相关技巧：首先定义快慢指针：快指针：用来寻找值不为val的元素。慢指针：用来更新新数组的下标
其含义一定要理解。具体什么意思：fast一直在数组循环，当找到值不为val的元素，就与slow交换，当fast遍历完整个数组，那么slow所代表的数组以内就都会是符合要求的值了。
class Solution:
def removeElement(self, nums: List, val: int) -> int:
# 快慢指针
fast = 0# 快指针
slow = 0# 慢指针
size = len(nums)
while fast < size:# 不加等于是因为，a = size 时，nums 会越界
# slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
if nums != val:
nums = nums
slow += 1
fast += 1
return slow删除有序数组中的重复项
26. 删除有序数组中的重复项 - 力扣（LeetCode）
相关技巧：相信大家如果认真的解过移除元素的题目，那么这题将十分简单。同样的定义快慢指针：快指针：向后遍历数组中的元素如果与当前元素重复即继续遍历。慢指针：用来更新数组使得到慢指针指向的位置无重复元素。
class Solution:
def removeDuplicates(self, nums: List) -> int:
slow,fast=0,1
while fast<len(nums):
if nums!=nums:
nums=nums
slow=slow+1
fast+=1
return slow+1字符串篇
反转字符串
344. 反转字符串 - 力扣（LeetCode）
相关技巧：相信做到做到现在，做了这么多双指针法的题目，这种应该能够一眼看出怎么做了，定义双指针从两端一同向中间遍历交换即可。
class Solution:
def moveZeroes(self, nums: List) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
start,end=0,0
while end<len(nums):
if nums!=0:
nums,nums=nums,nums
start+=1
end+=1替换数字
54. 替换数字（第八期模拟笔试）
相关技巧：替换数字成number，这里我们看如果我们正常的去做就是使用额外的空间，从原数组开始遍历，字母直接进入，数字变成number。那么我们能不能原地操作呢？双指针法就可帮你实现。但是有个细节，我们快慢指针的初始位置，快指针在扩充后的数组的末尾，慢指针在数组原来的最后一个元素上，然后慢指针向前遍历，快指针跟着向前，慢指针的字母直接到快指针位置，数字变成number在放在快指针位置，示意图如下：
class Solution:
def sortedSquares(self, nums: List) -> List:
left,right,n=0,len(nums)-1,len(nums)
sorted=*n
while left<=right:
if pow(nums,2)<=pow(nums,2):
sorted=pow(nums,2)
right-=1
else:
sorted=pow(nums,2)
left+=1
n-=1
return sorted四数之和
18. 四数之和 - 力扣（LeetCode）
# 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) -> Optional:
pre,cur=None,head
while cur:
tmp=cur.next
cur.next=pre
pre=cur
cur=tmp
return pre算法基础系列
一文了解什么是数组及其经典考察题目
走进链表及其经典考察题目
还不知道什么是哈希表，看这篇文章就够了
字符串匹配究极大招【KMP】:带你一步步从原理到构建
【栈与队列】：基础实战篇
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]