# 資訊

:::info
- Question: 2958. Length of Longest Subarray With at Most $k$ Frequency
- From: Leetcode Daily Challenge 2024.03.28
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

You are given an integer array `nums` and an integer `k`.

The **frequency** of an element `x` is the number of times it occurs in an array.

An array is called **good** if the frequency of each element in this array is less than or equal to `k`.

Return the length of the longest good subarray of `nums`.

A subarray is a contiguous non-empty sequence of elements within an array.

> Example 1:
:::success
- Input: `nums = [1,2,3,1,2,3,1,2]`, `k = 2`
- Output: 6
- Explanation: The longest possible good subarray is `[1,2,3,1,2,3]` since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays `[2,3,1,2,3,1]` and `[3,1,2,3,1,2]` are also good. It can be shown that there are no good subarrays with length more than 6.
:::

> Example 2:
:::success
- Input: `nums = [1,2,1,2,1,2,1,2]`, `k = 1`
- Output: `2`
- Explanation: The longest possible good subarray is `[1,2]` since the values 1 and 2 occur at most once in this subarray. Note that the subarray `[2,1]` is also good. It can be shown that there are no good subarrays with length more than 2.
:::

> Example 3:
:::success
- Input: `nums = [5,5,5,5,5,5,5]`, `k = 4`
- Output: 4
- Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray. It can be shown that there are no good subarrays with length more than 4.
:::

> Constraints:
:::success
- 1 <= `nums.length` <= $10^5$
- 1 <= `nums[i]` <= $10^9$
- 1 <= `k` <= `nums.length`
:::

---

# 解法

## 概念

還是 sliding window，不過比昨天簡單一點點

基本上就是在 window 裡面的數值 frequency 一定會小於等於 `k`，如果超過我的第 10 - 18 行就會跳出來，跳出 while 迴圈應該就是計算答案並進到下一輪，而下一輪就是 `l+1` 這樣而已

小細節嘛。。其實 sliding window 要注意範圍問題，或說甚麼時候停下來，像這邊第 8 行就是 `l<n`，因為 `l` 要走到 `n-1` 的位置，而不是看 `r`，這邊要注意一下！

然後我要寫到睡著了。。

## 程式碼

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        freq = { nums[0]: 1 }
        l = 0
        r = 1
        ans = 1
        n = len( nums )
        while l < n:
            # r Move to the right most
            while r < n:
                if nums[r] not in freq:
                    freq[nums[r]] = 1
                    r += 1
                elif nums[r] in freq and freq[nums[r]] < k:
                    freq[nums[r]] += 1
                    r += 1
                else:
                    break

            # Modify ans
            if ( r - l ) > ans:
                ans = r - l

            # Shift l one unit
            freq[nums[l]] -= 1
            l += 1
        return ans

---

# 複雜度

## 時間複雜度

因為使用了 sliding window，基本上 `l` 會一直往後跑，`r` 也是，而且跑過的不會再重複跑一次，因為我沒有 `l` 往下扣或 `r` 往下扣的機制，所以會是 $O(2n) = O(n)$


## 空間複雜度

空間的話因為有一個字典，所以是 $O(n)$