你有一條彩虹色的彩帶，但是因為它是異世界來的彩帶，所以可能不只 7 個顏色 (異世界有可能有 87 色的彩虹)，你有一個定義彩帶美麗度的標準，你定義一條彩帶的美麗度為它所擁有的長度為 M 且有 M 種顏色的子區間數量。
現在你需要寫一個程式來計算一個字串的美麗度。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有兩個數字 M 和 N，代表定義的子區間長度和彩帶長度。 第二行有 N 個數字代表彩帶的顏色。 | 輸出這條彩帶的美麗度。 |
| 3 7 1 2 3 5 4 5 4 | 3 |
解題思路
因為數字最大會是 10 的 150 次方，所以要用字串的方式來收彩帶的數字。使用 Map 來紀錄每個區間的數字數量，並且宣告一個變數 number 來紀錄目前的區段中有多少個不同的數字。
跑一個 For迴圈 從 0 到 N-1，並且每次都將新的資料紀錄到 Map 中並且把最左邊的資料做刪除，如果刪除的資料中的 Map 值是 0，那就 number–，代表區段中少了一個不同的數字。並且如果新加入的數字的 Map 值是 1，代表是一個全新的數字 number++，每次迴圈都要判斷 number 是否等於 M，如果有等於的話就將答案 +1。
範例程式碼－ZeroJudge e289: 美麗的彩帶
#include <iostream>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int M, N;
string num[200000] = {};
map<string, int>appear;
cin >> M >> N;
for (int i = 0; i<N; i++) {
cin >> num[i];
}
int count = 0, last = 0, ans = 0, number = 0;
for (int i = 0; i<N; i++) {
const string current = num[i];
if (count <= M-1) {
appear[current]++;
count++;
if (appear[current] == 1) number++;
if (number == M) ans++;
}
else {
appear[num[last]]--;
if (appear[num[last]] == 0) number--;
appear[current]++;
if (appear[current] == 1) number++;
last++;
if (number == M) ans++;
}
}
cout << ans << "\n";
}
//ZeroJudge E289
//Dr. SeanXD