[LeetCode] - 2958. Length of Longest Subarray With at Most K Frequency

https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-frequency/description/

Leetcode - Length of Longest Subarray With at Most K Frequency

문제 유형 : 슬라이딩 윈도우, 해시

문제 난이도 : Medium

 

문제

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.

 

정수 배열 nums와 정수 k를 받습니다.

모든 요소의 빈도가 k보다 작은 부분배열의 최대 길이를 구하시오.

 

풀이

슬라이딩 윈도우를 이용하여 쉽게 풀 수 있다.

슬라이딩 윈도우의 맨 왼쪽 포인터와 맨 오른쪽 포인터를 만든다. 각각 i, j라고 하겠다. 둘다 0부터 시작한다.

해시맵을 만들어서, 요소의 빈도를 저장시킨다.

 

j를 다음으로 보내면서, nums[j]의 빈도를 1 증가시킨다.

만약 nums[j]가 k보다 커진다면,  nums[j]가 k보다 작거나 같아질때까지 슬라이딩 윈도우의 크기를 줄여야 한다.

nums[i]의 빈도를 1 줄이면서, i를 다음으로 보낸다. 이를 nums[j]가 k보다 큰 동안 반복한다.

 

매번 위 과정을 한 번씩 거치고, 최대 길이의 수를 업데이트한다.

 

그리고, 순회가 끝나면 최대 길이를 반환한다.

 

코드

C++

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        const int n = nums.size();
        unordered_map<int, int> mp;
        int maxLength = 0;

        for(int i = 0 , j = 0; j < n; j++) {
            mp[nums[j]]++;

            while(mp[nums[j]] > k) {
                mp[nums[i]]--;
                i++;
            }
            maxLength = max(maxLength, j - i + 1);
        }

        return maxLength;
    }
};