目錄
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";elsecout<<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;
}
????????
????????
?????????
)
