2958. Length of Longest Subarray With at Most K Frequency

nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6

/*
 * 演算法 / Algorithm: 滑動視窗 + 自製雜湊表 (Sliding window + hand-written hash map).
 * 用左右指針框出目前視窗，雜湊表記錄每個值在視窗內的出現次數。
 * Right pointer grows the window; when the just-added value's count exceeds k,
 * advance left until it's valid again. Answer is the largest window length seen.
 * 時間 O(n)，空間 O(n)。Time O(n), space O(n).
 */

#include <stdlib.h>   // malloc, calloc, free (動態記憶體 / dynamic memory)

/* --- 一個極簡的「值 -> 次數」開放定址雜湊表 --- */
/* --- A minimal open-addressing hash map from value -> count --- */
typedef struct {
    long *keys;    // 存放鍵（也就是 nums 的值）/ stores keys (the nums values)
    int  *vals;    // 對應的計數 / the matching counts
    char *used;    // 該格是否已被占用 (1=用了, 0=空) / is this slot occupied
    int   cap;     // 桶子總數，取 2 的次方方便用位元遮罩取模 / bucket count, a power of two
} Map;

// 建立一個容量為 cap 的雜湊表 / build a hash map with capacity cap
static Map map_new(int cap) {
    Map m;
    m.cap  = cap;                        // 記住容量 / remember capacity
    m.keys = malloc(sizeof(long) * cap); // 配置鍵陣列 / allocate keys array
    m.vals = calloc(cap, sizeof(int));   // calloc 會把計數清成 0 / calloc zeroes the counts
    m.used = calloc(cap, sizeof(char));  // calloc 把 used 全設為 0=空 / all slots start empty
    return m;
}

// 用完後釋放記憶體，避免記憶體洩漏 / free memory afterwards to avoid leaks
static void map_free(Map *m) {
    free(m->keys);  // 釋放鍵陣列 / free keys
    free(m->vals);  // 釋放值陣列 / free vals
    free(m->used);  // 釋放占用旗標 / free used flags
}

// 找到 key 該待的桶子索引 (若不存在則回傳一個空桶) / find the slot for key (or an empty one)
static int map_slot(Map *m, long key) {
    // 用位元 AND 取代取模：因為 cap 是 2 的次方，key & (cap-1) 等同 key % cap
    // Bitwise AND as a fast modulo: since cap is a power of two, key & (cap-1) == key % cap
    int i = (int)(((unsigned long)key * 1000000007UL) & (m->cap - 1));
    // 線性探測：若桶子被別的鍵占用，就看下一格 / linear probing to next slot on collision
    while (m->used[i] && m->keys[i] != key) {
        i = (i + 1) & (m->cap - 1);      // 前進一格並回繞到頭 / step forward, wrap around
    }
    return i;                            // 回傳最終落腳的桶子 / return the resting slot
}

// 把 key 的計數加上 delta（可為 +1 或 -1），並回傳更新後的計數
// Add delta (+1 or -1) to key's count, return the new count
static int map_add(Map *m, long key, int delta) {
    int i = map_slot(m, key);            // 找到桶子 / locate the slot
    if (!m->used[i]) {                   // 若這是第一次遇到這個 key / first time we see this key
        m->used[i] = 1;                  // 標記占用 / mark occupied
        m->keys[i] = key;                // 寫入鍵 / store the key
        m->vals[i] = 0;                  // 計數從 0 開始 / count starts at 0
    }
    m->vals[i] += delta;                 // 更新計數 / update the count
    return m->vals[i];                   // 回傳新計數給呼叫者判斷 / return new count to caller
}

int maxSubarrayLength(int* nums, int numsSize, int k) {
    // 桶子數取大於 2*numsSize 的最小 2 次方，確保夠鬆、探測快
    // Pick a power-of-two capacity comfortably larger than the data to keep probing fast
    int cap = 1;
    while (cap < numsSize * 2) cap <<= 1; // cap 左移一位就是乘 2 / left shift doubles cap
    Map count = map_new(cap);            // 建立計數表 / build the count map

    int left = 0;                        // 視窗左端點 / window's left boundary
    int ans  = 0;                        // 目前最長好子陣列的長度 / best length so far

    // right 是視窗右端點，一步步向右擴張 / right pointer expands the window one step at a time
    for (int right = 0; right < numsSize; right++) {
        // 把新元素加入視窗，計數 +1，並拿到它的新頻率
        // Add the new element into the window (+1) and read back its new frequency
        int freq = map_add(&count, nums[right], +1);

        // 只有「剛加入的這個值」可能超標；若超過 k 就從左邊縮小視窗
        // Only the just-added value can break the rule; if it exceeds k, shrink from the left
        while (freq > k) {
            // 移除最左邊元素：計數 -1，然後 left 右移 / drop leftmost: count -1, then advance left
            map_add(&count, nums[left], -1);
            left++;                      // 左端點右移，視窗變小 / move left boundary rightwards
            // 重新讀取「剛加入值」目前的頻率，看看是否已合法
            // Re-check the just-added value's current frequency to see if it's now legal
            freq = map_add(&count, nums[right], 0); // delta=0 表示只查詢不改動 / delta 0 = query only
        }

        // 到這裡視窗一定合法；用它的長度更新答案 / window is valid now; update the answer
        int len = right - left + 1;      // 視窗長度 = 右 - 左 + 1 / window length
        if (len > ans) ans = len;        // 取較大者 / keep the maximum
    }

    map_free(&count);                    // 釋放雜湊表記憶體 / free the hash map
    return ans;                          // 回傳最長好子陣列的長度 / return the answer
}

/*
 * 演算法 / Algorithm: 滑動視窗 + unordered_map 計數 (Sliding window + hash map counting).
 * 右指針擴張視窗，unordered_map 記錄每個值在視窗內的頻率；
 * Right pointer grows the window; the map tracks each value's frequency in the window.
 * 當剛加入的值頻率超過 k，就右移左指針縮小視窗，直到合法。
 * When the just-added value exceeds k, shrink from the left until valid.
 * 時間 O(n)，空間 O(n)。Time O(n), space O(n).
 */

#include <vector>          // std::vector 動態陣列 / dynamic array
#include <unordered_map>   // std::unordered_map 雜湊表 / hash map
#include <algorithm>       // std::max 取最大值 / for std::max

class Solution {
public:
    int maxSubarrayLength(std::vector<int>& nums, int k) {
        // unordered_map<int,int>：鍵是元素值，值是它在視窗內的出現次數
        // key = element value, value = its count inside the current window
        std::unordered_map<int, int> count;

        int left = 0;   // 視窗左端點 / left boundary of the window
        int ans  = 0;   // 目前最長合法視窗長度 / best window length so far

        // 用範圍索引讓 right 從 0 掃到最後 / right pointer sweeps left to right
        for (int right = 0; right < (int)nums.size(); ++right) {
            // count[nums[right]]++ 會在鍵不存在時自動建立並初始化為 0，再加 1
            // Indexing a missing key auto-creates it at 0, then ++ makes it 1
            count[nums[right]]++;

            // 只有剛加入的值可能超標；超過 k 就從左邊縮小視窗
            // Only the newly added value can exceed k; if so, shrink from the left
            while (count[nums[right]] > k) {
                // 移除最左元素：對應計數 -1，然後 left 右移
                // Drop the leftmost element: decrement its count, then advance left
                count[nums[left]]--;
                ++left;   // 左端點右移，視窗縮小 / move left boundary rightwards
            }

            // 此刻視窗保證合法；用其長度更新答案 / window is valid; update the answer
            // std::max 回傳兩者中較大者 / std::max returns the larger of the two
            ans = std::max(ans, right - left + 1);
        }

        return ans;   // 回傳最長好子陣列的長度 / return the length of the longest good subarray
    }
};