数据结构-双指针法

介绍 

双指针法是一种可以在O（n）时间复杂度内解决数组、链表、字符串等数据结构相关的问题的方法。核心思想为使用两个指针在不同位置遍历数组或链表，从而实现特定操作。

常见的双指针法有

1.快慢指针：快指针每次移动两步，慢指针移动一步，用于判断链表是否有环或者找到链表中间结点等；

2.左右指针：左指针指向数组开头，右指针指向结尾，用于解决二分查找、两数之和等等；

3.滑动窗口：维护一个特定窗口，用两个指针表示左右边界，寻找符号要求的子序列；

4.对撞指针：左指针从起始位置开始遍历，右指针从末尾遍历，满足条件的情况下移动左右指针，用于解决回文串等问题

滑动窗口指针例题

洛谷P1638 逛画展

我们需要用两个指针来维护一个没有最小的、具备所有画师作品的子序列，首先就需要先设置左指针指在开头，右指针不断向右移动，每次移动后判断是否满足具备所有画师作品，再找出其中最短的子序列

#include <bits/stdc++.h>
using namespace std;
int a[1000001];
int b[10000]={0};
int main() {
	int n,m;
	cin>>n>>m;
	int res=1,len=n;
	int s,e;
	for (int i=1; i<=n; i++) cin>>a[i];
	int l=0;//从左端开始寻找
	int r=0;
	b[a[0]]=1;
	while(r<=n&&l<=r) {//在所有样例中开始用滑动窗口查找
		if (res==m) {//当具备所有画师画作时
			if (len>r-l+1) {//找出最小区间并记录。题中要求找出第一个最小区别，因此不加等号
				len=r-l+1;
				s=l;
				e=r;
			}
			b[a[l]]--;//窗口向左边缩进，继续向右寻找
			if (b[a[l]]==0) res--;
			l++;
		} else {
			r++;//当不具备所有画师画作时，窗口向右延展
			if (b[a[r]]==0) res++;
			b[a[r]]++;
		}
	}
	cout<<s+1<<" "<<e+1;
	return 0;
}

洛谷P8783 [蓝桥杯2022省B]统计子矩阵 

这道题目难点在于能想到将它压缩为一维数列，当压缩为一维数列时，利用滑动窗口可以实现符号要求的子序列的查找。每次寻找的符合要求的边界，直接加上其中的子矩阵数，就可以得到总数

#include <bits/stdc++.h>
using namespace std;
long long a[501][501];//注意数据类型
long long b[501];
long long sum[510][510];//记录前缀和
signed main() {
	long long n,m,k;
	cin>>n>>m>>k;
	for (long long i=1; i<=n; i++) {
		for (long long j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
 
	for (long long j=1; j<=m; j++) {
		for (long long i=1; i<=n; i++) {
			sum[i][j]=sum[i-1][j]+a[i][j];//计算前缀和
		}
	}
	long long res=0;
	for (long long i=1; i<=n; i++) {
		for (long long j=i; j<=n; j++) {
			for (long long c=1; c<=m; c++)
				b[c]=sum[j][c]-sum[i-1][c];
			long long l=1,r=0;//开始利用双指针寻找子矩阵
			long long s=0;//记录所找矩阵中数值总和
			while(r<m) {
				r++;
				s+=b[r];
				if (s<=k) {//小于等于目标值，则继续移动
					res+=r-l+1;//每次移动，多出的满足条件的矩阵数为r-l+1
				} else {
					while(s>k) {//和大于时目标值，窗口从左边进行压缩
						s-=b[l];
						l++;
					}
					res+=r-l+1;
				}
			}
		}
	}
	cout<<res<<endl;
	return 0;
}