1. Two Sum

Input:  nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9 → 回傳索引 [0,1]

// 演算法 / Algorithm:
// 用雜湊表（key=數值, value=索引）掃一遍陣列；對每個元素先查它的互補值是否已出現，
// 有就回傳兩個索引，否則把當前元素存入。平均 O(n) 時間。
// One pass with a hash map (number→index): for each element look up its complement;
// if found, return both indices, else insert the current element. Average O(n) time.

#include <stdlib.h>   // malloc / free 等記憶體函式 / memory functions

// 雜湊表的一個節點：存一個 (數值, 索引)，並用鏈結串列處理碰撞
// One hash-table node: holds a (value, index) pair; uses a linked list for collisions
typedef struct Node {
    long long key;        // 數值本身 / the number itself
    int idx;              // 它在 nums 裡的索引 / its index in nums
    struct Node *next;    // 指向同一個桶裡的下一個節點 / next node in same bucket
} Node;

// LeetCode 規定：回傳的陣列要用 malloc 配置，並透過 returnSize 告知長度
// LeetCode requires: return a malloc'd array and report its length via returnSize
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    // 答案一定是 2 個索引，先配置 2 個 int 的空間 / answer is always 2 indices
    int* result = (int*)malloc(2 * sizeof(int));
    *returnSize = 2;   // 透過指標把長度寫回給呼叫者 / write length back via pointer

    // 桶的數量；取大於 numsSize 的數可減少碰撞。+1 避免 numsSize 為 0 時除以 0
    // Number of buckets; larger than numsSize to reduce collisions. +1 avoids divide-by-0
    int buckets = numsSize * 2 + 1;

    // 配置一個指標陣列當作桶；calloc 會把所有指標初始化為 NULL（空桶）
    // Allocate a pointer array as buckets; calloc zero-initializes them to NULL (empty)
    Node** table = (Node**)calloc(buckets, sizeof(Node*));

    for (int i = 0; i < numsSize; i++) {
        // 用 long long 避免 target - nums[i] 在極端值時溢位 / avoid overflow with long long
        long long complement = (long long)target - nums[i];

        // 把互補值映射到某個桶；取絕對值與取餘數確保落在 [0, buckets) 範圍
        // Map complement to a bucket; abs + modulo keeps it within [0, buckets)
        int h = (int)(llabs(complement) % buckets);

        // 走訪這個桶的鏈結串列，找有沒有等於 complement 的節點
        // Walk the linked list in this bucket, looking for a node equal to complement
        for (Node* p = table[h]; p != NULL; p = p->next) {
            if (p->key == complement) {       // 找到互補值了 / complement found
                result[0] = p->idx;           // 較早出現的那個索引 / the earlier index
                result[1] = i;                // 當前索引 / the current index
                // 提早回傳；此處不釋放 table 以保持範例精簡（程式結束後 OS 會回收）
                // Early return; we skip freeing table here for brevity (OS reclaims on exit)
                return result;
            }
        }

        // 沒找到互補值，就把「當前數值 → 當前索引」插入它自己的桶
        // Not found: insert "current value → current index" into its own bucket
        long long key = nums[i];                       // 當前數值 / current value
        int hi = (int)(llabs(key) % buckets);          // 算出當前數值該放哪個桶 / its bucket
        Node* node = (Node*)malloc(sizeof(Node));      // 配置一個新節點 / allocate a node
        node->key = key;                               // 填入數值 / set value
        node->idx = i;                                 // 填入索引 / set index
        node->next = table[hi];                        // 頭插法：接到桶原本的串列前面 / push front
        table[hi] = node;                              // 讓桶指向新節點 / bucket now points here
    }

    // 題目保證一定有解，理論上不會走到這裡 / problem guarantees a solution exists
    return result;
}

// 演算法 / Algorithm:
// 用 unordered_map（數值→索引）掃一遍；對每個元素先查互補值是否已存在，
// 有就回傳兩索引，否則把當前元素存入。平均 O(n) 時間。
// One pass with an unordered_map (value→index): look up each complement first;
// return both indices if present, else insert the current element. Average O(n).

#include <vector>          // std::vector，動態陣列 / dynamic array
#include <unordered_map>   // std::unordered_map，雜湊表 / hash map

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        // seen 把「看過的數值」對應到「它的索引」/ maps each seen value to its index
        std::unordered_map<int, int> seen;

        // range-for：依序取出每個索引 i，從 0 到 nums.size()-1
        // range-based loop over indices 0 .. nums.size()-1
        for (int i = 0; i < (int)nums.size(); i++) {
            // 算互補值；nums[i] 與 target 都在 int 範圍，差值也在 int 範圍，不會溢位
            // complement fits in int because both operands are within int range
            int complement = target - nums[i];

            // find 在雜湊表裡查 complement；找不到會回傳 end() 這個特殊迭代器
            // find() looks up complement; returns end() iterator if absent
            auto it = seen.find(complement);
            if (it != seen.end()) {          // 找到互補值 / complement exists
                // it->second 是該互補值存的索引；連同當前 i 一起回傳
                // it->second is the stored index; return it together with current i
                return { it->second, i };    // 用大括號直接建構回傳的 vector / brace-init vector
            }

            // 沒找到就記錄當前數值與索引，供後面的元素查詢
            // Not found: record current value→index for later elements to look up
            seen[nums[i]] = i;
        }

        // 題目保證有解，這行只是讓編譯器滿意 / guaranteed solution; satisfies the compiler
        return {};
    }
};