// 演算法 / 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;
}