一轮复习——B.双指针模型总结
注：双指针是个模型，不局限于必须两个指针，三个、四个指针也是一样的，本质在于降低暴力求解的时间复杂度，以下的双指针模型时间复杂度均为O(N)
思维导图概览
同向双指针
大多利用到数的单调性（需有序）或正负性
例题：
优选算法-双指针：2.复写零（重点题）
👆归纳原因：利用位置性：直接定位到最终位置，反遍历
👆归纳原因：利用单调性+正负性：第一次正遍历找正数的（负数自动跳过），另一次反遍历找负数的（正数自动跳过）
明显利用单调性的：
明显利用位置性的：
①分区间处理
分区间处理：[0,dest][dest+1,cur-1][cur+1,n-1]
分别是[已处理的非0][已处理的0][待处理]
例题：
优选算法-双指针：1.移动零（重点题）
👆归纳原因：找到两个指针下标所在区间加以判断
👆归纳原因：分为[递增区间][可移除递增子数组][递增区间]
👆归纳原因：思路跟2970一摸一样
②快慢双指针
主要用于找中点、判断
例题：
优选算法-双指针：3.快乐数（重点题）
👆归纳原因：通过快慢指针的相遇点判断快乐数
③求两点A、B间距离
prev标记A上个位置，遍历B，如果当前数等于A就更新
用prev!=-1判断A是否出现过来决定是否更新
例题：
异向双指针
本质：利用位置性
①对撞双指针
首尾双指针往里缩，逐步判断，同向双指针的缩影，本质就是利用位置性
例题：
优选算法-双指针：4.盛水最多的容器（重点题）
优选算法-双指针：5.有效三角形的个数（重点题）
优选算法-双指针：6.和为s的两个数字（重点题）
优选算法-双指针：7.三数之和（重点题）
优选算法-双指针：8.四数之和（重点题）
②中心扩展双指针
找到一个符合题意得点，左右扩展，本质也是利用位置性
例题：
👆归纳原因：找到正负数的节点，利用正数平方依旧升序，负数平方降序的特点解题
其他
题目及解析👇
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
18
0- 0
已为社区贡献6条内容
所有评论(0)