什么是双指针算法
双指针是指在遍历元素时，不是使用单个指针进行遍历而是使用两个指针进行访问，从而达到相应目的；注意这个指针不是c语言中那个指向地址的指针；
双指针分类
双指针分为对撞指针和快慢指针；
对撞指针：两个指针方向相反，例如你需要用两个指针去遍历一个数组，一个从数组起始点开始进行遍历，一个指针是从最后开始遍历；
快慢指针：快慢指针是方向相同，例如一个数组都是从数组起始的地方进行遍历或者都是从尾部进行遍历，快慢指针又称为弗洛伊德算法，兔子乌龟算法；
快慢指针常用判别链表中是否有环
接下来用题目详细介绍这两种算法
对撞指针
对撞指针常用于解决那些问题
有序数组两数之和
二分查找
三数之和(无序）
最接近的三数之和
有序数组两数之和
例题链接：. - 力扣（LeetCode）
题目描述：
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例
输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
先上代码
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i=0;
int j=numbers.size()-1;
while(i<j)
{
int sum=numbers[i]+numbers[j];
if(sum<target)
i++;
else if(sum>target)
j--;
else
return vector<int>{i+1,j+1};
}
return vector<int>{-1,-1};
}
};解释一下这段代码就是题目已经告诉我们按非递减顺序排好了，那就说明数组已经按照递增顺序排好了；接下来就是按照要求求和，这个数组右边是最大值，左边是最小值，那就设两个指针进行遍历，在这段代码中设的就是i和j，分别给i和j赋值，在这里,numbers[i]就是这个数组的最小值，numbers[j]就是这个数组的最大值，然后相加，将相加的值与目标值进行比较，如果小于目标值说明需要将值增大，就要将i向右移，因为右边的值大于左边的值，如果大于同理就要让这个值小一点，所以r向左移，如果相等说明找到了就返回；
三数之和(无序)
有人会疑惑，三数之和双指针怎么去满足，看看下面的题去解释
题目：三数之和
题目链接：. - 力扣（LeetCode）
题意：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
先看代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n=nums.size();
sort(nums.begin(),nums.end());
vector<vector<int>> ans;
for(int first=0;first<n;first++)
{
if(first>0&&nums[first]==nums[first-1])
continue;
int third=n-1;
int target=-nums[first];
for(int second=first+1;second<n;second++)
{
if(second>first+1&&nums[second]==nums[second-1])
continue;
while(second<third&&nums[second]+nums[third]>target)
{
third--;
}
if(second==third)
break;
if(nums[second]+nums[third]==target)
ans.push_back({nums[first],nums[second],nums[third]});
}
}
return ans;
}
};在此解释一下这段代码，先将数组进行排序，排完之后在设置一个vector的容器；然后就是三层循环最主要的是那两个for循环，第一个for循环循环first的指向，将first不断向前移动，这里面的双指针分别是second和third,third赋值为n-1就是将third置为数组的最右边，将目标值减去nums[first]的值，那么目标值就是second和third值之和，然后开始进行移动两个指针，如果值大于目标1值说明需要third的值向左移因为左边的值要小，往左移，移到second等于third说明所有的值都大于目标值那直接就退出最里面的for循环说明在移second也没有用了因为second的值是往右移的，值一直增大，后面的值会更大于目标值target，找到符合的值就假如到ans容器中到最后进行返回；
二分查找
二分查找就不再举例子了，因为二分查找中本来就蕴含了双指针的思想，他本来就设两个指针，一边是在数组的最左边，一个指针指向数组最右边，所以不再说了，这属于二分算法中的一环了；
快慢指针
快慢指针有龟兔赛跑的名字，非常的亲切；
快慢指针运用的领域
快慢指针可以利用在链表中也可以运用在数组中；
运用在链表中有以下几种运用的方式
1.判断环形链表
2.找出倒数第k个结点
3.找出链表中间结点
4.找到环形链表的的入口（进阶）
5. 相交链表
1.判断环形链表
题目链接：. - 力扣（LeetCode）
题意
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head) {
if(head==NULL||head->next==NULL)
return false;
struct ListNode *slow=head,*fast=head->next;
while(slow!=fast)
{
if(fast->next==NULL||fast->next->next==NULL)
{
return false;
}
fast=fast->next->next;
slow=slow->next;
}
return true;
}判断环形链表是快慢指针的典型题目，在有环链表如果它有环，快指针每次走两步，慢指针每次走一步那么有环他们必定相遇，注意一定要是快指针走两步，慢指针每次走一步，如果走别的步数可能就不能去辨别了；为什么呢？这里涉及到数学问题了，原来计算机的尽头真的是数学啊，
走一步，那么快指针比慢指针每次多走一步是1的倍数那么如何它们都会相遇；
如果快指针每次走三步那么，快指针每次比慢指针走2步，那么就不是1的倍数了，而一个奇数无论减几个偶数它都是奇数，它们就不会相遇，同样偶数也是如此，所以快慢指针中慢指针走一步而快指针走两步是最好的结果；
2.找出倒数第k个结点
题目链接：https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/
题意：给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
示例1：
输入：head = [2,4,7,8], cnt = 1 输出：8
代码：
ListNode* trainingPlan(ListNode* head, int cnt) {
ListNode* l,*r;
l=r=head;
if(head==NULL)
return NULL;
for(int i=0;i<cnt;i++)
r=r->next;
while(r!=nullptr)
{
r=r->next;
l=l->next;
}
return l;
}解释一下这段代码，就是让快指针先移步k个结点(注意代码中ans就是k)，然后快指针与慢指针一起移动当快指针移到空的时候，慢指针到达的位置就是倒数第k个位置(倒数第ans个位置)，为什么呢? 这里需要涉及相关的数学公式列方程
假如链表的长度是n，那么在头指针到这个位置就是(n-k)，那么当一个指针移动n-k个位置时就到达了倒数第k个位置，那么快指针先移动了k个位置那它剩下的就是n-k个位置，那么这时候慢指针和快指针一起移动，当快指针为空的时候，慢指针就到达了第k个位置了；
3.找出链表中间结点
题目链接：. - 力扣（LeetCode）
题意：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
代码：
ListNode* deleteMiddle(ListNode* head) {
if (head->next==nullptr) {
return nullptr;
}
ListNode* r=head;
ListNode* l=head;
ListNode* pre=nullptr;
while(l&&l->next)
{
l=l->next;
l=l->next;
pre=r;
r=r->next;
}
pre->next=pre->next->next;
return head;
}解析一下这段代码，这个就是快指针走两步，慢指针走一步，那么当快指针走完之后，慢指针刚好到达中点；
下面举两个例子分别分析奇数和偶数个数的情况
当数是奇数个
1->2->3->4->5
快指针和慢指针都从1开始走，当快指针走到5的时候，慢指针刚好到达3也就是中间位置，这个时候快指针的条件就是r->next==NULL
当数的个数是偶数个时
1->2->3->4->5->6
快指针和慢指针都从1开始走，当快指针走到6后面的时候，慢指针刚好到达4满足条件的位置，这个时候，快指针的条件就是r==NULL;
所以这段代码整体的意思就影刃而解了
4.找到环形链表入口
题目链接：. - 力扣（LeetCode）
题意：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
代码
ListNode *detectCycle(ListNode *head) {
ListNode *slow=head,*fast=head;
while(fast!=nullptr){
slow=slow->next;
if(fast->next==nullptr)
return nullptr;
fast=fast->next->next;
if(fast==slow){
fast=head;
while(fast!=slow)
{
fast=fast->next;
slow=slow->next;
}
return slow;
}
}
return nullptr;
}在这里先解释一下这道题的原理：把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili
这个视频解释的非常清楚不理解的可以看看，因为我这里没有图就不做多的解释了，本来想尝试画一下图感觉太抽象了；
解释一下这段代码吧，就是先看看这fast或者fast->next是不是为空，因为fast一下挑两格，所以有可能是fast为空也有可能fast->next为空，之后就是fast一下走两步,slow每次走一步，当slow和fast第一次相遇时将fast置为head，在此相遇时就是入口，这里还是数学公式的推导，视频里很详细；
5.相交链表
提名链接：. - 力扣（LeetCode）
题意：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案
示例1
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
代码
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
// 计算链表 A 和链表 B 的长度
int lenA = 0, lenB = 0;
ListNode *tempA = headA, *tempB = headB;
while (tempA != nullptr) {
lenA++;
tempA = tempA->next;
}
while (tempB != nullptr) {
lenB++;
tempB = tempB->next;
}
// 将指针移动到使它们的长度相等的位置上
tempA = headA;
tempB = headB;
if (lenA > lenB) {
int diff = lenA - lenB;
while (diff-- > 0) {
tempA = tempA->next;
}
} else {
int diff = lenB - lenA;
while (diff-- > 0) {
tempB = tempB->next;
}
}
// 遍历链表直到找到交点
while (tempA != nullptr && tempB != nullptr) {
if (tempA == tempB) {
return tempA;
}
tempA = tempA->next;
tempB = tempB->next;
}
return nullptr; // 没有交点
}解析一下这段代码
先通过循环求出两个链表的长度，然后让比较长的那个链表，先走一段距离使两个链表到最后的结点的长度是相同的，然后遍历两个链表，相等了就是相遇了就表示有交点，否则就没有交点；
题例
多说无益，以题见真章
这段题目是综合进阶的题目
逛画展
题目链接：逛画展 - 洛谷
题意：
博览馆正在展出由世上最佳的 mm 位画家所画的图画。
游客在购买门票时必须说明两个数字，aa 和 bb，代表他要看展览中的第 aa 幅至第 bb 幅画（包含 a,ba,b）之间的所有图画，而门票的价钱就是一张图画一元。
Sept 希望入场后可以看到所有名师的图画。当然，他想最小化购买门票的价格。
请求出他购买门票时应选择的 a,ba,b，数据保证一定有解。
若存在多组解，输出 aa 最小的那组。
输入格式：
第一行两个整数 n,mn,m，分别表示博览馆内的图画总数及这些图画是由多少位名师的画所绘画的。
第二行包含 nn 个整数 aiai，代表画第 ii 幅画的名师的编号。
输出格式：
一行两个整数 a,ba,b。
输入输出样例
输入
12 5 2 5 3 1 3 2 4 1 1 5 4 3
输出
2 7
代码如下
#include<iostream>
using namespace std;
int cnt,ans,n,m,a[1000005],b[1000005],ansl,ansr;
void I(int x)
{
if(b[x]==0)
{
cnt++;
}
b[x]++;
}
void D(int x)
{
if(b[x]==1)
{
cnt--;
}
b[x]--;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ans=n;
for(int l=1,r=1;r<=n;r++)
{
I(a[r]);
while(true)
{
D(a[l]);
if(cnt==m)
l++;
else
{
I(a[l]);
break;
}
}
if(cnt==m&&r+1-l<ans)
{
ans=r+1-l;
ansl=l;
ansr=r;
}
}
if(ansl!=0)
cout<<ansl<<" "<<ansr;
else
cout<<1<<" "<<ans;
return 0;
}这是一道快慢指针类型的题目；
解释一下代码，题目要求的是将全部画家的画包含在内并且要求包含的画最小，注意它只能按照顺序去看而不能跳级去看，那么就定义两个指针，两个指针都指向数组的开始，然后先向数组中添加一副画，然后r是一直向后移动的，然后就是将l这副画删除然后去判断是否满足条件，如果满足条件就将l指向的这幅画删除，如果不行在把这幅画添上，然后就这样一直判断最后输出相应的数组，其实我感觉这道题不是明确的快慢指针；
在进阶
统计子矩阵
这道题是用了二维数组，需要将它压缩为一维数组之后，在进行指针移动
题目链接：[蓝桥杯 2022 省 B] 统计子矩阵 - 洛谷
题意：
给定一个 N×MN×M 的矩阵 AA，请你统计有多少个子矩阵 (最小 1×11×1, 最大 N×M)N×M) 满足子矩阵中所有数的和不超过给定的整数 KK。
输入格式：
第一行包含三个整数 N,MN,M 和 KK。
之后 NN 行每行包含 MM 个整数, 代表矩阵 AA。
输出格式：
一个整数代表答案。
输入输出样例
输入
3 4 10 1 2 3 4 5 6 7 8 9 10 11 12
输出
19
代码如下
#include<iostream>
#define int long long
using namespace std;
int a[505][505],s[505][505],ans;
int b[505];
signed main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>a[i][j];
}
for(int j=1;j<=m;j++)
{
for(int i=1;i<=n;i++)
s[i][j]=s[i-1][j]+a[i][j];
} //求行之间的前缀和
for(int ii=1;ii<=n;ii++)
{
for(int i=ii;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
b[j]=s[i][j]-s[ii-1][j];
}
int l=1,r=0,sum=0;
while(r<m)
{
r++;
sum+=b[r];
if(sum<=k)
ans+=(r-l+1);
else
{
while(sum>k){
sum-=b[l];
l++;
}
ans+=(r-l+1);
}
}
}
}
cout<<ans;
return 0;
}解释一下这段代码算是快慢指针中的一道类型题吧
先将二维数组按列求出前缀和，然后用三个嵌套循环，前两个循环用于行之间的相减，最后一个循环用于列之间的相减，就是行之间对应进行相减就是s[1][1]-s[0][1]以此类推，将它们的值加入到一个一维数组当中，它这个循环就是先是第一行的值减第零行的值，之后就是将第二行的值减去第零行的值.....之后第二行减第一行，第三行减去第一行；之后得到一个一维数组，在用两个指针，进行遍历，第一个指针在前面如果两个位置在的数组的数相减小于k那就加上r-l+1,为啥加一因为r从0开始的，也就是快指针从0开始的而慢指针是从0开始的，为什么是r-l，注意这个数组代表的前缀和，所以当这两个区间相加小于目标值那么原来这个数组它本身的值就小于目标值；
双指针就先到这了，自我感觉总结的并不好，感觉有的知识点知道但是不知道这么说，我在研究研究将它完善完善；
