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