【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e289
【解題想法】Two Pointers【筆記】
- 數字介於 0 ~ 10150 之間：讀入測資後，以字串形式儲存。
- 使用unordered_map，加快讀取速度。（因為key不需要排序。）
#include <iostream>
#include <unordered_map>
using namespace std;
string a[200005];
unordered_map < string, int > mp;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, n;
while (cin >> m >> n){
for (int i = 0; i < n; i++){
cin >> a[i];
}
mp.clear();
int cnt = 0;
for (int i = 0; i < m; i++){
if (!mp[a[i]]) cnt++;
mp[a[i]]++;
}
int ans = (cnt == m);
for (int L = 0, R = m; R < n; L++, R++){
mp[a[L]]--;
if (mp[a[L]] == 0) cnt--;
if (mp[a[R]] == 0) cnt++;
mp[a[R]]++;
ans += (cnt == m);
}
cout << ans << "\n";
}
}
Python 程式碼 (credit: Amy Chou)
while True:
try:
m, n = map(int, input().split())
S = list(map(str, input().split()))
dic = {}
color = 0;
for i in range(m):
if S[i] not in dic.keys():
color += 1
dic[S[i]] = dic.get(S[i], 0) + 1
if (color == m):
ans = 1
else:
ans = 0
L = 0
R = m
while (R < n):
dic[S[L]] -= 1
if (dic[S[L]] == 0):
color -= 1
if (dic.get(S[R], 0) == 0):
color += 1
dic[S[R]] = dic.get(S[R], 0) + 1
if (color == m):
ans += 1
L += 1
R += 1
print(ans)
except:
break;