// 演算法 / Algorithm:
// 用雜湊表記住「每個數值最後出現的索引」，從左到右掃一遍；
// 遇到重複值時，比較它和上次索引的距離是否 <= k。
// Use a hash map storing each value's last index; scan once and check the gap.
//
// LeetCode 沒有內建雜湊表，這裡用「開放定址法」自己實作一個簡單的雜湊表。
// LeetCode's C has no hash map, so we hand-roll one using open addressing.

#include <stdbool.h>   // 提供 bool / true / false 型別 / gives us bool, true, false
#include <stdlib.h>    // 提供 malloc, free / for malloc and free
#include <string.h>    // 提供 memset / for memset

bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
    // 雜湊表容量取大於資料量的 2 的次方，減少碰撞 / capacity > n, power of two, fewer collisions
    int cap = 1;                          // 容量從 1 開始 / start capacity at 1
    while (cap < numsSize * 2) cap <<= 1; // 左移一位 = 乘 2，直到夠大 / shift left = ×2 until big enough
    int mask = cap - 1;                   // cap 是 2 次方時，x & mask 等同 x % cap / fast modulo via bitmask

    // keys 存數值，idxs 存對應的索引，used 標記某格是否被佔用
    // keys holds values, idxs holds their indices, used marks whether a slot is taken
    int*  keys = (int*)  malloc(sizeof(int)  * cap);  // 配置記憶體 / allocate memory
    int*  idxs = (int*)  malloc(sizeof(int)  * cap);  // 配置記憶體 / allocate memory
    bool* used = (bool*) calloc(cap, sizeof(bool));   // calloc 會把記憶體清成 0/false / zero-initialized

    bool answer = false;                  // 預設答案為 false / default answer

    for (int i = 0; i < numsSize; i++) {  // 逐一掃描每個元素 / scan each element
        int v = nums[i];                  // 目前的數值 / current value
        // 計算起始雜湊槽；轉成 unsigned 避免負數取模出問題 / hash slot; cast to unsigned to avoid negative issues
        unsigned int h = ((unsigned int) v) & mask;

        // 線性探測：若該槽被佔用且 key 不同，就往後找下一個空槽或相同 key
        // Linear probing: if slot is taken by a different key, move to the next slot
        while (used[h] && keys[h] != v) {
            h = (h + 1) & mask;           // 往後移一格並繞回開頭 / step forward, wrap around
        }

        if (used[h]) {                    // 找到相同的值，代表之前出現過 / value seen before
            if (i - idxs[h] <= k) {       // 因 i 一定比舊索引大，不需 abs / i is always larger, so no abs needed
                answer = true;            // 距離在範圍內，找到答案 / within range, found it
                break;                    // 提早結束迴圈 / stop early
            }
            idxs[h] = i;                  // 否則更新成最新索引，下次比較才最近 / refresh to newest index
        } else {                          // 此值第一次出現 / first time seeing this value
            used[h] = true;               // 標記此槽已佔用 / mark slot as used
            keys[h] = v;                  // 存入數值 / store the value
            idxs[h] = i;                  // 存入索引 / store the index
        }
    }

    free(keys);                           // 釋放記憶體，避免外洩 / free memory to avoid leaks
    free(idxs);                           // 同上 / same
    free(used);                           // 同上 / same
    return answer;                        // 回傳最終結果 / return the result
}