双指针例题

AcWing 799. 最长连续不重复子序列

题目链接 视频讲解链接

1.给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续区间，输出它的长度。 输入格式 第一行包含整数n。 第二行包含n个整数（均在0~100000范围内），表示整数序列。 输出格式 共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。 数据范围 1≤n≤100000 输入样例： 5 1 2 2 3 5 输出样例： 3

在一个数组内的双指针

#include<iostream> #include<cstring> using namespace std; const int N = 100010; int a[N]; int vis[N];//计数 int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n; memset(vis,0,sizeof(vis)); for(int i=0;i < n;i ++) cin>>a[i]; int ans = 0; for(int i=0,j=0;i<n;i++) { vis[a[i]]++; while(vis[a[i]]>1) { vis[a[j]]--; j++; } ans = max (ans , i - j + 1); } cout<<ans<<endl; return 0; }

AcWing 800. 数组元素的目标和

两个数组的双指针 下面题目解法视频链接

2.给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。 请你求出满足A[i] + B[j] = x的数对(i, j)。 数据保证有唯一解。 输入格式 第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。 第二行包含n个整数，表示数组A。 第三行包含m个整数，表示数组B。 输出格式 共一行，包含两个整数 i 和 j。 数据范围 数组长度不超过100000。 同一数组内元素各不相同。 1≤数组元素≤109 输入样例： 4 5 6 1 2 4 7 3 4 6 8 9 输出样例： 1 1

#include<iostream> using namespace std; const int N = 100010; int a[N]; int b[N]; int n,m,x; int main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>x; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<m;i++) cin>>b[i]; for(int i=0,j=m-1;i<n;i++) { while(j>=0&&a[i]+b[j]>x) j--; if(a[i]+b[j]==x) { cout<<i<< " "<<j<<endl; break; } } return 0; }

leetcode1208. 尽可能使字符串相等

题目链接点击此处

3.给你两个长度相同的字符串，s 和 t。 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。

用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。

如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。

如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。

示例 1： 输入：s = “abcd”, t = “bcdf”, cost = 3 输出：3 解释：s 中的 “abc” 可以变为 “bcd”。开销为 3，所以最大长度为 3。

示例 2： 输入：s = “abcd”, t = “cdef”, cost = 3 输出：1 解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3： 输入：s = “abcd”, t = “acde”, cost = 0 输出：1 解释：你无法作出任何改动，所以最大长度为 1。

提示： 1 <= s.length, t.length <= 10^5 0 <= maxCost <= 10^6 s 和 t 都只含小写英文字母。

#include<iostream> using namespace std; int main() { string s,t; int maxcost,cost=0; cin>>s>>t>>maxcost; int n=s.size(); int ans=0; for(int i=0,j=0;i<n;i++) { cost+=abs(s[i]-t[i]); while(cost>maxcost) { cost -= abs(s[j]-t[j]); j++; } ans=max(ans,i-j+1); } return ans; } class Solution { public: int equalSubstring(string s, string t, int maxCost) { int ans=0,cost=0,n=s.size(); for(int i=0,j=0;i<n;i++) {//固定窗口 cost+=abs(s[i]-t[i]); while(cost>maxCost){//窗口溢出，需要缩小窗口 cost-=abs(s[j]-t[j]); j++; } ans=max(ans,i-j+1); } return ans; } };