LeetCode 解題筆記：2958. Length of Longest Subarray With at Most K Frequency

作者：王一哲
日期：2026年8月12日


LeetCode 題目連結：2958. Length of Longest Subarray With at Most K Frequency

解題想法

中等難度題。題目給一個整數陣列 $nums$ 及一個整數 $k$，要找出 $nums$ 之中的最長連續子陣列，且子陣列之中每個數字出現的次數小於等於 $k$。這題很適合用滑動視窗 (sliding window) 解題。

1. $nums$ 的長度為 $n$，視窗左端點 $left$ 起始值為 $0$，答案 $ans$ 預設為 $0$，用字典 $cnt$ 記錄視窗範圍內的數字數量。
2. 用一層 for 迴圈跑視窗右端點 $right = 0$ 到 $right = n-1$，$cnt[nums[right]] += 1$。
3. 再用一層 while 迴圈，如果 $left < right$ 且 $cnt[nums[right]] > k$ 繼續執行，移除左端點的數字 $cnt[nums[left]] -= 1$，左端點向右移 1 格 $left += 1$。
4. 跑完 while 迴圈時，$nums[right]$ 到 $nums[left]$ 之間的數字數量都小於等於 $k$，視窗長度為 $right - left + 1$，這可能是新的答案，更新 $ans$。

Python 程式碼

用 defaultdict 比較方便。Runtime: 262 ms, beats 44.51%. Memory: 35.44 MB, beats 15.77%.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        left = 0  # 視窗左邊界
        ans = 0  # 答案
        cnt = defaultdict(int)  # 視窗範圍內數字計數器
        for right in range(n):  # 視窗右邊界依序為 0 ~ n-1
            cnt[nums[right]] += 1  # 右邊界數字數量加 1
            # 如果左邊界小於右邊界，右邊界數字數量大於 k
            while left < right and cnt[nums[right]] > k:
                cnt[nums[left]] -= 1  # 左邊界數字數量減 1
                left += 1  # 左邊界向右移 1 格
            ans = max(ans, right - left + 1)  # 更新答案
        return ans

用預設的 dict，更新 $nums[right]$ 的數量時需要先檢查 $nums[right]$ 是否在 $cnt$ 之中，比較麻煩一點。Runtime: 262 ms, beats 44.51%. Memory: 35.20 MB, beats 94.91%.

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 長度
        left = 0  # 視窗左邊界
        ans = 0  # 答案
        cnt = dict()  # 視窗範圍內數字計數器
        for right in range(n):  # 視窗右邊界依序為 0 ~ n-1
            # 右邊界數字數量加 1
            if nums[right] not in cnt:
                cnt[nums[right]] = 1
            else:
                cnt[nums[right]] += 1
            # 如果左邊界小於右邊界，右邊界數字數量大於 k
            while left < right and cnt[nums[right]] > k:
                cnt[nums[left]] -= 1  # 左邊界數字數量減 1
                left += 1  # 左邊界向右移 1 格
            ans = max(ans, right - left + 1)  # 更新答案
        return ans

C++ 程式碼

Runtime: 51 ms, beats 95.95%. Memory: 149.29 MB, beats 84.27%.

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int n = (int)nums.size(), left = 0, ans = 0;  // 長度，視窗左邊界，答案
        unordered_map<int, int> cnt;  // 視窗範圍內數字計數器
        for(int right = 0; right < n; right++) {  // 視窗右邊界依序為 0 ~ n-1
            cnt[nums[right]]++;  // 右邊界數字數量加 1
            // 如果左邊界小於右邊界，右邊界數字數量大於 k
            while(left < right && cnt[nums[right]] > k) {
                cnt[nums[left]]--;  // 左邊界數字數量減 1
                left++;  // 左邊界向右移 1 格
            }
            ans = max(ans, right - left + 1);  // 更新答案
        }
        return ans;
    }
};

用 map 速度很慢，因為這題只需要計數、不需要排序，建議使用 unordered_map。Runtime: 192 ms, beats 9.44%. Memory: 150.55 MB, beats 17.36%.

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int n = (int)nums.size(), left = 0, ans = 0;  // 長度，視窗左邊界，答案
        map<int, int> cnt;  // 視窗範圍內數字計數器
        for(int right = 0; right < n; right++) {  // 視窗右邊界依序為 0 ~ n-1
            cnt[nums[right]]++;  // 右邊界數字數量加 1
            // 如果左邊界小於右邊界，右邊界數字數量大於 k
            while(left < right && cnt[nums[right]] > k) {
                cnt[nums[left]]--;  // 左邊界數字數量減 1
                left++;  // 左邊界向右移 1 格
            }
            ans = max(ans, right - left + 1);  // 更新答案
        }
        return ans;
    }
};