e289 - 美麗的彩帶

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一條長度為 n 的彩帶中，有多少個長度為 m 的子區間包含 m 種不同的顏色。彩帶的顏色由輸入的數字序列表示。

解題思路

本題可以使用滑動窗口 (Sliding Window) 搭配雜湊表 (Hash Table) 來解決。我們維護一個大小為 m 的窗口，並使用雜湊表記錄窗口內各顏色的出現次數。當窗口滑動時，我們更新雜湊表，並檢查窗口內顏色的種類數是否等於 m。如果等於 m，則將美麗度加一。

具體步驟如下：

1. 讀取 m 和 n。
2. 使用雜湊表 a 記錄每個顏色的出現次數。
3. 遍歷彩帶的每個顏色。
4. 將當前顏色的出現次數加一。
5. 如果窗口大小超過 m，則將最左邊顏色的出現次數減一。如果該顏色的出現次數降至 0，則從雜湊表中移除該顏色。
6. 如果窗口大小達到 m，且雜湊表中的顏色種類數等於 m，則將美麗度加一。
7. 輸出美麗度。

複雜度分析

• 時間複雜度: O(n)，其中 n 是彩帶的長度。因為我們需要遍歷彩帶一次。
• 空間複雜度: O(m)，其中 m 是子區間的長度。因為雜湊表最多存儲 m 種不同的顏色。

程式碼

#include <iostream>
#include <map>
using namespace std;
map <string,int> a;
int n,m,ans,it;
string cn,tmp[200001];
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> m >> n;
	for(int i=0;i<n;++i){
		cin >> cn;
		++a[cn];
		tmp[i]=cn;
		if(i>=m){
			--a[tmp[it]];
			if(a[tmp[it]]==0)
				a.erase(tmp[it]);
			++it;
		}
		if(i>=m-1)
			if(a.size()==m)
				++ans;
	}
	cout << ans; 
}