2958-LengthOfLongestSubarrayWithAtMostKFrequency.go

package main

// 2958. Length of Longest Subarray With at Most K Frequency
// 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:
// 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:
// 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:
// 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:
//     1 <= nums.length <= 10^5
//     1 <= nums[i] <= 10^9
//     1 <= k <= nums.length

import "fmt"

// 滑动窗口 + 哈希表
func maxSubarrayLength(nums []int, k int) int {
	m := make(map[int]int)
	left, res := 0,0
    max := func (a int, b int) int { if a > b { return a; }; return b; }

	for right, x := range nums {
        // 哈希表维护每个元素在窗口个数
		m[x]++
        // 维护窗口内数组元素个数不超过 k 即可
		for m[x] > k {
			m[nums[left]]--
			left++
		}
		res = max(res, right - left + 1)
	}
	return res
}

func main() {
    // 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.
    fmt.Println(maxSubarrayLength([]int{1,2,3,1,2,3,1,2},2)) // 6

    // 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.
    fmt.Println(maxSubarrayLength([]int{1,2,1,2,1,2,1,2},1)) // 2

    // 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.
    fmt.Println(maxSubarrayLength([]int{5,5,5,5,5,5,5}, 4)) // 4

    fmt.Println(maxSubarrayLength([]int{1,2,3,4,5,6,7,8,9}, 4)) // 9
    fmt.Println(maxSubarrayLength([]int{9,8,7,6,5,4,3,2,1}, 4)) // 9
}