[LeetCode] 992. Subarrays with K Different Integers

https://leetcode.com/problems/subarrays-with-k-different-integers/

Leetcode - Subarrays with K Different Integers

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

문제 난이도 : Hard

 

문제

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

• For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

 

정수 배열 nums와 정수 k가 주어진다. 요소의 종류가 정확히 k개 있는 부분배열의 개수를 구하시오.

 

풀이

기본적인 슬라이딩 윈도우로 접근하려고 하면... 

최소 조건을 만족한 채로 오른쪽으로 가고, 왼쪽 포인터를 옮기자니, 이러면 다음의 가능성들도 없애는 꼴이 되어버린다.

 

그래서, 시각을 바꿔보기로 해보자.

최대 k개의 종류를 가진 부분배열들의 개수를 구한다.

그 뒤, 최대 k-1개의 종류를 가진 부분배열들의 개수를 구하여 뺀다.

 

그러면 정확히 k개의 종류를 가진 부분배열들의 개수가 나온다.

 

코드

C++

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        int K = subarray_with_atmost_k(nums, k);
        int K_1 = subarray_with_atmost_k(nums, k-1);

        return K - K_1;
    }

    int subarray_with_atmost_k(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> mp;
        int left = 0, right = 0, ans = 0;
        while(right < n) {
            mp[nums[right]]++;
            while(mp.size() > k) {
                mp[nums[left]]--;
                if(mp[nums[left]] == 0) mp.erase(nums[left]);
                left++;
            }

            ans += right - left + 1;
            right++;
        }

        return ans;
    }
};