双指针

参考资料

• 双指针 - OI Wiki

简介

双指针（Two Pointers）同时维护两个下标（指针），通过同向或相向移动来维护区间信息或统计答案，避免暴力枚举的重复计算。

最常见的用法是「滑动窗口」：对具有单调性的区间信息（如正整数之积、元素之和），固定右端点 $r$ 向右移动，当条件不满足时收缩左端点 $l$，每步操作 $O(1)$，两指针各最多移动 $n$ 次，总时间复杂度 $O(n)$。

另一类用法是在有序数组上「相向移动」：$l$ 从左端出发，$r$ 从右端出发，根据当前值与目标的大小关系分别向内逼近，同样 $O(n)$ 求解。

双指针也是莫队算法的基础：离线排序后，用两个指针记录当前区间，逐步扩缩转移答案。

实现

以「无重复字符的最长子串」为例：给定字符串 $s$，求不含重复字符的最长连续子串长度。

337 Bcpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin>>s;
	int n=s.size(),ans=0;
	int cnt[128]={};
	for(int l=0,r=0;r<n;r++)
	{
		cnt[(int)s[r]]++;
		while(cnt[(int)s[r]]>1)
		{
			cnt[(int)s[l]]--;
			l++;
		}
		ans=max(ans,r-l+1);
	}
	cout<<ans<<'\n';
	return 0;
}

例题

洛谷 P1102 A-B 数对

给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A-B=C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。

洛谷 P1366 有序表的合并

给出两个数列 $a,b$，均按不降序排序。其中保证 $a$ 中没有重复的数字。

现在请你求出：$a$ 中每一个数字在 $b$ 中出现了几次？