題目： UVa - 11572 - Unique Snowflakes

題目說明

給一串數字代表雪花的編號，編號不同的雪花代表形狀不同，求一次最多能裝出多少個不同的雪花，只能按照順序裝，不可跳過任意的雪花。

Input： 測資起始於一個整數 n，代表有 n 組資料，每組資料起始於一個整數 N，代表有 N 片雪花，接下來 N 行每行會有一個數字，代表雪花的編號。

Output： 輸出能最多能裝出的雪花的個數。

解題思路

題目其實就是在求一個陣列中最長的不重複子陣列，依此想法去解題即可。r 為當前讀取到的元素個數。

解法一：使用 DP 及 Sliding window 的概念，使用 Unordered_map 儲存每個數字最後出現的 index，每次讀取一個元素時，先判斷是否已經存在於 map，若存在則 Window 的 l 需更新為 l、及該 index + 1 兩者的較大者，此時 Window 的長度為 r - l + 1，接著更新該元素在 map 中的 index，並且更新 ret。

解法二：使用 Unordered_set 及 Vector 依序儲存讀取到的元素，使用一個整數 l 從 0 開始記數，每次讀取一個元素時，先判斷該元素是否在 set 中出現過，若出現則在 set 中刪除 v[l] 並將 l 加一，直到 set 中沒有該元素為止，此時 Window 的長度為 r - l + 1，接著將元素存入 set 中。

參考解法

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int N, tmp, l = 0, r = 0, ret = 0;
        unordered_map<int, int> m;
        cin >> N;
        while (N--)
        {
            cin >> tmp;
            if (m.count(tmp)) l = max(l, m[tmp] + 1);
            ret = max(ret, r - l + 1);
            m[tmp] = r;
            ++r;
        }
        cout << ret << '\n';
    }
}

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int N, tmp, l = 0, r = 0, ret = -1;
        vector<int> v;
        unordered_set<int> s;
        cin >> N;
        while (N--)
        {
            cin >> tmp;
            while (s.count(tmp)) s.erase(v[l++]);
            s.insert(tmp);
            v.emplace_back(tmp);
            ret = max(r - l + 1, ret);
            ++r;
        }
        cout << ret << '\n';
    }
}