題意#
題目給定包含 \( n \) 首歌的播放清單，每首歌有專屬的數字 ID。
我們要從清單中擷取一段連續的歌曲片段。
條件是該片段內不可有 ID 相同的歌曲。
我們需要求出最長的「不重複連續片段」包含幾首歌。
思路#
尋找「最長不重複連續子陣列」為標準的滑動視窗（Sliding Window）問題。
使用右指標 rdx 逐步擴展視窗，並以 set 記錄視窗內出現過的歌曲 ID：
- 若新歌未出現於
set，將其加入，並更新最大視窗長度。 - 若新歌已在
set中，代表有重複歌曲，必須縮減視窗左邊界。將左指標ldx指向的歌曲逐出視窗（並移出set），直到將重複的歌曲也移出為止，恢復視窗內無重複的狀態。
滑動視窗藉由右側推進與左側縮減，能於單次掃描中找出最長目標序列。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n; vector<int> v(n);
for (auto &i : v) cin >> i;
// st 用來記錄當前滑動視窗內出現過哪些歌
set<int> st; int mx = -1e9;
// 使用雙指標 ldx 和 rdx 來維護滑動視窗
for (int ldx = 0, rdx = 0; rdx < n; rdx++) {
// 如果當前這首歌已經在視窗內了
if (st.count(v[rdx]))
// 不斷將左邊界的歌移出視窗，直到包含重複的那首歌為止
do {st.erase(v[ldx]);} while (v[ldx++] != v[rdx]);
// 把當前這首歌正式加入視窗中
st.insert(v[rdx]);
// 更新歷史最大視窗長度
mx = max(mx, (int)st.size());
}
// 輸出最長不重複片段的長度
cout << mx << '\n';
}
