[算法每日一练]-双指针 （保姆级教程篇 1） #A-B数对 #求和 #元音字母 #最短连续子数组 #无重复字符的最长子串 #最小子串覆盖 #方块桶

目录

A-B数对

解法一：双指针?

解法二：STL二分查找

解法三：map

求和

元音字母

最短连续子数组

无重复字符的最长子串

最小子串覆盖

方块桶

---

????????

双指针特点：双指针绝不回头

????????

????????

A-B数对

????????

解法一：双指针?

?先把数列排列成递增的就可以使用双指针了。找到满足a[r]-a[l]=c即可

?对每个l找对应的两个r，一个是满足条件且在最左边的，一个是满足条件且在最右边的

?如果刚好可以取等，那么右减左就是该情况下的答案，否则右减左就是0

#include <bits/stdc++.h>            
#define ll long long      
using namespace std;       
const int N = 2e5 + 10;
int n , c;
int a[N];
int main () 
{
	cin >> n >> c;
	for(int i = 1 ; i <= n ; i ++) cin >> a[i];
	sort(a + 1 , a + 1 + n);      //首先就必须要排序
	int l = 1, r1 = 1 , r2 = 1;
	ll ans = 0;
	for(l = 1 ; l <= n ; l ++) {
		while(r1 <= n && a[r1] - a[l] <= c) r1 ++;//对每一个数A找右边刚不满足A-B=C的数下标
		while(r2 <= n && a[r2] - a[l] < c ) r2 ++;//再找左边刚满足A-B=C的数下标
			ans += r1 - r2;
	}
	cout << ans;
	return 0;
}

解法二：STL二分查找

在有序数组找某个数不用stl用什么？

#include <bits/stdc++.h>
using namespace std;
int N, C, A[200010];

int main() {
	scanf( "%d%d", &N, &C );
	for( int i = 1; i <= N; ++i ) scanf( "%d", &A[ i ] );
	sort( A + 1, A + N + 1 );
	long long ans = 0;
	for( int i = 1; i <= N; ++i ) 
		ans += upper_bound( A + 1, A + N + 1, A[ i ] - C ) - 
			lower_bound( A + 1, A + N + 1, A[ i ] - C );
	printf( "%lld\n", ans );
	return 0;
}

解法三：map

既然要同一个值得数量，那么就拿数值存下标，说错了。这样会爆掉的，直接上map进行离散化数组就行了，什么意思？就是你别拿一个连续的玩意去存，你拿一个离散的东西去存就行了。

#include <iostream>             //A-B数对P1102   (map映射法)   （有点耗时）
#include <unordered_map>                  //A-B=C --> A-C=B
using namespace std;
typedef long long LL;
LL a[200001];
unordered_map<LL,LL> m;       //建立一个数字到出现次数的映射 map<num,times>
int main() {
    int n; LL c;LL ans=0;
    cin >> n >> c;    
    for(int i=1;i<=n;i++) {
        cin >> a[i];    
        m[a[i]]++;     //标记每个数字和对应的映射
        a[i]-=c;       //把first减c，找更新后映射的数量
    } 
    for(int i=1;i<=n;i++) ans+=m[a[i]];
    cout << ans << endl;
    return 0;
}

????????

?????????

求和

求满足和为x所有的自然数区间，如果没有输出No

????????

思路：

对每个l开头的区间尝试求解。

双指针移动时：[l,r]恰好为x就说明[l,r+1]和[l+1,r]没用了，所以整体右移l++,r++

[l,r]<x就r右移，[l,r]>x就l右移(这次的l已经没用了)

然后就是注意一下结束条件l<=x/2

#include <bits/stdc++.h>
using namespace std;
int main(){
	int x,l=1,r=2,sum=0;
	cin>>x;int f=0;
	while(l<=x/2){ //这个结束条件很有意思：l<=x/2就没必要再找了
		sum=(l+r)*(r-l+1)/2;
		if(sum==x){
			f=1;
			cout<<l<<" "<<r<<'\n';
			l++;r++;
		}
		else if(sum<x)r++;
		else l++;
	}
	if(!f)cout<<"No";
}

????????

????????

元音字母

给一个字符串s和整数k，求s的长度为k的子串可能包含的最大元音字母个数

输入? ? ? ? ? ? ? ? ? ? ? ? ? ? ?输出：3
abciiidef
????????

思路：

[l,r]一定是整体移动的，所以只需要观察l和r+1情况即可，如果都是或都不是，cnt不变直接不管；剩下的就是cnt++和cnt--了

#include <bits/stdc++.h>
using namespace std;
int check(char ch){
	if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')return true;
	return false;
}
int main(){
	string s;int k;
	cin>>s>>k;
	int l=0,r=k-1,ans=0,cnt=0,len=s.size();
	for(int i=0;i<k;i++){
		if(check(s[i]))cnt++;//初始化
	}
	ans=cnt;
	while(r<len){//整体移动一次就判断一次
		if(!check(s[l])&&check(s[r+1]))cnt++;
		if(check(s[l])&&!check(s[r+1]))cnt--;
		l++;r++;
		ans=max(ans,cnt);
	}
	cout<<ans;
}

????????

????????

最短连续子数组

给一个含有n个非负数的数组和一个正整数m。找出该数组中满足和不小于m的长度最小的连续子数组，并返回其长度，否则返回0

输入? ? ? ? ? ? ? ? ?输出：2
6 7
2 3 1 2 4 3

????????

思路：

?在移动过程中[l,r]如果满足条件的话，一定要l++来取最小长度，否则就r++即可。

（一直都是r在默默前行，l只需要统计结果即可）

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,a[N],ans=0x3f3f3f3f;

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int sum=0;
	for(int l=0,r=0;r<=n;r++){
		sum+=a[r];
		while(sum>=m){
			ans=min(ans,r-l+1);
			sum-=a[l];
			l++;
		}
	}
	cout<<(ans==0x3f3f3f3f ? 0 : ans);
}

????????

????????

无重复字符的最长子串

给一个字符串s，找出其中不含有重复字符的最长字串的长度。
abcabcbb
????????

思路：

?首先使用map<char,int>来统计每个字符出现次数，一遍统计一遍检查是否有重复字符。

如果有，对于[l,r]就l++，直到没有再r++

#include <bits/stdc++.h>
using namespace std;
unordered_map<char,int>ma1;
string s;
int ans=0;
int main(){
	getline(cin,s);
	int len1=s.size();
	for(int l=0,r=0;r<len1;r++){
		ma1[s[r]]++;
		while(ma1[s[r]]==2){
			ma1[s[l]]--;l++;
		}
		ans=max(ans,r-l+1);
	}
	cout<<ans;
}

????????

????????

最小子串覆盖

给两个字符串s,t，求s中最短的包含t每一个字符的子串，若不存在就返回No
输入

ADOBECODEANXBC? ? ? ? ? ? ? ? 输出ANXBC
BANC

????????

思路：

不是找子序列啊，注意看样例。

首先要统计t字符串的字符情况，然后在对s字符串使用双指针时候，也要统计区间中的字符情况，同时记录和t字符串的字符满足个数：对应字符数量相等。

当[l,r]中已经满足条件时候，就l++取找答案，同时对应的字符数量减一，直到不满足再r++。

????????

#include <bits/stdc++.h>
using namespace std;
unordered_map<char,int>ma1,ma2;
string s,t;
int ans=0x3f3f3f3f;
int main(){
	cin>>s>>t;
	int len1=s.size(),len2=t.size();
	for(int i=0;i<len2;i++)
		ma2[t[i]]++;
	int sum=0;//sum表示满足的个数
	int l=0,r=0,ll=0,rr=0;
	while(r<len1){
		ma1[s[r]]++;
		if(ma2[s[r]]!=0&&ma1[s[r]]<=ma2[s[r]])//是t的字符，且s的数量不多余
			sum++;
		if(sum==len2){
			while(ma1[s[l]]>ma2[s[l]]){//从左开始删掉多余的，l++一次删掉一次
				ma1[s[l]]--;l++;
			}
			if(r-l+1<ans){
				ans=r-l+1;
				ll=l;rr=r;//ll和rr是上次答案对应的左右指针
			}
		}
		r++;
	}	
	if(ans==0x3f3f3f3f) cout<<"No";
	else
		cout<<s.substr(ll,rr-ll+1);
}

????????

????????

方块桶

给n个非负整数表示连续n个竖直放置的方块，计算这样的方块可以装多少水？
12
0 1 0 2 1 0 1 3 2 1 2 1

????????

思路：

其实在模拟的时候发现左边这个高度下是否可以填水取决于右边的最大高度，右边更高，那么一定可以填水，右边同理。然后两条同时开始统计就行了

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],maxl,maxr,ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	maxl=a[1],maxr=a[n];
	int l=1,r=n;
	while(l<r){
		if(maxl<=maxr){
			l++;
			maxl=max(maxl,a[l]);
			ans+=maxl-a[l];
		}
		else{
			r--;
			maxr=max(maxr,a[r]);
			ans+=maxr-a[r];
		}
	}
	cout<<ans;
}

????????

????????

?????????