系列目標

許多人包括我，都會有程式學習到一個段落後就不知道要從哪個方向繼續學習的問題，若是程式學習過程中有觀念不理解、實作不熟，就容易導致後面的內容全部都學不好，因此此系列適合有C/C++程式基礎的讀者進行學習，例如已有輸入輸出、if else、迴圈、陣列、字串、遞迴等基本概念，往後30天，我們將由演算法核心概念出發，並搭配 CSES Problem Set 與 LeetCode 題庫進行實戰練習，有效提升理論知識以及實作能力。

學習路線將循序漸進：

• 第一週：熟悉 C++ STL、排序、雜湊、二分搜尋等基礎演算法
• 第二週：進入雙指標、貪心、BFS/DFS、圖論基礎
• 第三週：專攻動態規劃（DP），從基礎到進階題型
• 第四週：挑戰圖論進階、字串演算法與綜合實戰

我們將採用「理論解析 → C++ 實作 → 題目演練」的方式，
不僅讓讀者理解演算法的原理，更能在實際刷題中掌握解題技巧，
幫助你在 30 天內，從演算法入門者，逐步進階到能挑戰中等難度題目的程度。

Day 1 學習目標

• 熟悉 C++ 常見的 STL 容器與輸入輸出技巧。
• 學習使用vector、unordered_map 解決問題，體驗雜湊表在演算法中的應用。
• 體驗 CSES 與 LeetCode 題目的風格，建立解題思維。

STL是什麼?

在 C++ 中，STL（Standard Template Library，標準模板庫）提供了許多常用的資料結構與演算法，能幫助我們快速開發高效、可讀性強的程式。

常見的 STL 功能：

• 容器 (Containers) → 儲存資料，例：vector、array、set、map、unordered_map
• 演算法 (Algorithms) → 常見演算法的實作，例：sort()、binary_search()、lower_bound()、upper_bound()
• 迭代器 (Iterators) → 容器巡覽工具
• 函式物件 (Function Objects) → 自訂比較子、lambda

今天我們會用到兩種最重要的 STL 元件：
vector：動態陣列
unordered_map：雜湊表（Hash Table）

STL vector：動態陣列

vector 是最常用的 STL 容器之一，特別的地方是:

• 可以動態調整大小，不需要像普通陣列一樣事先固定長度。
• 提供高效的隨機存取 (O(1))
• 提供常見操作：新增、刪除、排序
  所以學會vector以後，幾乎可以取代我們以前使用的傳統陣列。

常見實作

vector<int> v;           // 宣告空vector
v.push_back(5);          // 在vector尾端加入元素
v.emplace_back(7);       // 與 push_back 類似，但效率更高
cout << v[0];            // 直接取值
cout << v.size();        // 取得元素數量
sort(v.begin(), v.end()); // 排序陣列(由小到大)

STL unordered_map：雜湊表

unordered_map 允許我們 用鍵(key)快速查找值(value)，適合處理等等會介紹的Leetcode: Two Sum 這類查找題。
特點:

• 平均查找時間複雜度 O(1)
• 元素是無序的，如果需要排序需改用 map
• 常用於計數、查重、快速比對

實作

unordered_map<string, int> mp;
mp["apple"] = 3;
mp["banana"] = 5;

if (mp.count("apple")) {   // 判斷鍵是否存在
    cout << mp["apple"];   // 輸出 3
}

實戰 1: CSES Distinct Numbers

原題:
https://cses.fi/problemset/task/1621

題意

給定 n 個整數，輸出這些數字中不同數字的數量。

#include <bits/stdc++.h>
using namespace std;

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

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    // 排序 + unique 去重
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    cout << nums.size() << endl;
    return 0;
}

去重功能詳細說明:
移動:

unique(nums.begin(), nums.end())

功能：移動重複元素到容器尾端，並回傳「不重複元素之後的第一個位置」。
註:unique() 不會刪除元素，只是重排，且使用前須先排序。
範例:

vector<int> v = {1, 2, 2, 3, 3, 3, 4};
auto it = unique(v.begin(), v.end());
// v = {1, 2, 3, 4, 3, 3, 4};  <-- 後面數值還在，但不再有意義
// it -> 指向「4 之後」的位置

刪除:

nums.erase(unique(nums.begin(), nums.end()), nums.end());

功能：刪除從 unique 回傳的位置到容器結尾的所有元素。這樣就能真正刪除多餘的重複元素，讓 vector 只保留唯一值。
範例:

vector<int> v = {1, 2, 2, 3, 3, 3, 4};
v.erase(unique(v.begin(), v.end()), v.end());
// v = {1, 2, 3, 4}  <-- 最終去重完成

實戰 2: Leetcode Two Sum

原題:
https://leetcode.com/problems/two-sum/description/

題意

給定陣列 nums 和目標值 target，找出兩個索引 i、j 使得 nums[i] + nums[j] = target。

題解

解法一:暴力解

vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target)
                return {i, j};
        }
    }
    return {};
}

解法二: 雜湊表O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 使用 unordered_map 來加速查找
        // key: 數值, value: 該數值在 nums 中的索引
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++) {
            int diff = target - nums[i];
            if (mp.count(diff)) { //之前是否出現過一個值 = diff
                return {mp[diff], i};
            }
            // 如果沒找到，將當前數字和索引加入 mp，之後遇到另一個數字時可以直接查找
            mp[nums[i]] = i;
        }
        return {};
    }
};