【C++】競程筆記（資料結構：Unordered set / map）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

簡介

Unordered set / map 皆為無序的（unordered）關聯式容器，內部實作原理皆是 Hash（雜湊），對於每次操作的時間複雜度都是 $O(1)$ 。如果此資料結構發生碰撞的話，最壞的時間複雜度會到 $O(n)$ 。

那既然都無序了，所以就字面上意思，輸出的元素不一定會照著順序排。

Unordered set / map 提供了較快的操作速度，在操作上面也與原本的 set / map 無異，基本上都相通。

另外兩者的標頭檔都有稍微更改：

1
2
#include <unordered_set>
#include <unordered_map>

雜湊（Hash）介紹

雜湊函式（英語：Hash function）又稱雜湊演算法，是一種從任何一種資料中建立小的數字「指紋」的方法。雜湊函式把訊息或資料計算成摘要，使得資料量變小，將資料的格式固定下來。該函式將資料打亂混合，重新建立一個叫做雜湊值（又叫雜湊值）（hash values，hash codes，hash sums，或hashes）的指紋。
From Wikipedia

詳細參考：https://ithelp.ithome.com.tw/articles/10208884

習題練習

Sum of Four Values

Source：https://cses.fi/problemset/task/1642

解題思路：

要找出四個索引 $i, j, k, l$ ，使得：

  • $i, j, k, l$ 必不同。
  • 任意順序輸出皆可。

如果用暴力解會是 $O(n^4)$ ，非常的可怕。

所以這邊用一個 Two Sum 的思路去解，就是兩數和+兩數和=四數和。

可以先把所有兩數和的組合及其對應的 index 存進一個表（hash table），然後遍歷所有可能的兩數組合，查詢是否存在另一個兩數組合，使總和為 x，並且四個 index 互不重複。

解題步驟：

  1. 建立 unordered_map<long long, vector<pair<int,int>>>：
    • Key 為 $a[i] + a[j]$ 。
    • Value 是所有產生此和的 $(i, j)$ 索引對。
  2. 再次列舉所有兩數組 $(k, l)$ ：
    • 查找 map 中是否有 $x - (a[k] + a[l])$ 的和存在。
    • 確保這四個索引互不相同。

第 29 行的 long long target = x - 1LL * a[i] - a[j];：

是為了用兩數和+兩數和=四數和的方法，原本的公式長成第一式那樣，第二式只是將 a[k] + a[l] 移項所得而已。

程式碼：

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
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    int n;
    long long x;
    cin >> n >> x;

    vector<int> a(n);
    for (int &num : a) cin >> num;

    // unordered_map 儲存所有 a[i] + a[j] 的組合與對應索引
    unordered_map<long long, vector<pii>> sum_map;

    // 列舉所有兩數和（把他們都加進去 unordered_map）
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // 1LL 轉成 long long
            long long sum = 1LL * a[i] + a[j];
            sum_map[sum].emplace_back(i, j); // 存入對應索引
        }
    }

    // 再次列舉所有兩數，查找對應的 target sum
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            long long target = x - 1LL * a[i] - a[j];
            if (sum_map.find(target) != sum_map.end()) {
                for (auto &[k, l] : sum_map[target]) {
                    // 確保四個索引互不相同
                    if (i != k && i != l && j != k && j != l) {
                        cout << i + 1 << " " << j + 1 << " " << k + 1 << " " << l + 1 << "\n";
                        return 0;
                    }
                }
            }
        }
    }

    cout << "IMPOSSIBLE\n";
    return 0;
}