// 演算法 / Algorithm:
// 用 unordered_map 記住每個數值最後出現的索引，掃描一遍；
// 遇到重複且距離 <= k 即回傳 true。
// Use unordered_map to store each value's last index; one pass, return true on a close repeat.

#include <vector>          // 提供 std::vector / for std::vector
#include <unordered_map>   // 提供 std::unordered_map（雜湊表）/ for std::unordered_map (a hash map)
using namespace std;

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        // unordered_map：鍵=數值，值=該數值最後出現的索引；平均 O(1) 查詢
        // unordered_map: key = value, value = its last index; average O(1) lookups
        unordered_map<int, int> lastSeen;

        // range-for + index：用傳統 for 才能拿到索引 i / classic for loop so we have index i
        for (int i = 0; i < (int) nums.size(); i++) {
            int v = nums[i];                      // 目前數值 / current value

            // find 回傳一個迭代器；若等於 end() 代表沒找到 / find returns an iterator; end() means not found
            auto it = lastSeen.find(v);
            if (it != lastSeen.end()) {           // 這個值之前出現過 / this value appeared before
                // it->second 是儲存的舊索引；i 一定較大，故不需 abs / it->second is the old index; i is larger
                if (i - it->second <= k) {
                    return true;                  // 距離在 k 內，找到答案 / within k, found it
                }
                it->second = i;                   // 更新成最新索引 / update to the newest index
            } else {
                lastSeen[v] = i;                  // 第一次出現，記下索引 / first occurrence, record index
            }
        }

        return false;                             // 掃完都沒找到 / nothing found after the full scan
    }
};