[Java/투포인터] LeetCode 992. Subarrays with K Different Integers

🤔 Intuition

체감상 어려워서 답을 참고했다. 막상 답을 보면 "간단하네..." 하는 문제를 마주하면 현타가 좀 오는데, 이번 문제도 그러했다.

 

counting array를 운영하는 부분수열 유형이므로 투포인터로 해결할 수 있음은 명료하다.

🔎 Algorithm & Complexity

* @algorithm two pointer
* @time O(N)
* @memory O(N)

👨🏻‍💻 Logic

직관적이면서 가장 빠른 풀이는 maxEnd와 minEnd를 운영하는 것이다. (3 ms)

1. right pointer를 +1씩 옮겨가면서 정확히 K개의 distinct elements로 구성된 가장 작은 subarray를 먼저 찾고, (right=minEnd)
2. righter pointer를 그 상황에서 distinct elements가 K개로 유지되는 한 +1씩 더 옮겨서 최대 길이를 찾는다. (right=maxEnd)
3. 각 left에 대한 maxEnd - minEnd + 1가 distinct elements가 K개인 subarray의 경우의 수이다.
4. 위 과정을 left++ 를 반복하며 구하면 된다.

import java.util.*;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int ans = 0, left = 0, right = 0;
        
        while (right < nums.length) {
            while (map.size() < k && right < nums.length) {
                map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
                right++;
            }
            // if distinct elements count == k : (below)
            int maxEnd = right;
            while (maxEnd < nums.length && map.getOrDefault(nums[maxEnd], 0) != 0) {
                maxEnd++;
            }
            while (map.size() == k) {
                ans += maxEnd - right + 1;
                if (map.get(nums[left]) == 1) {
                    map.remove(nums[left]);
                } else {
                    map.put(nums[left], map.get(nums[left]) - 1);
                }
                left++;
            }
        }
        return ans;
    }
}

 

조금 기발한 아이디어로 푸는 방법도 있었다. (46ms)

distinct elements의 개수가 K인 subarrays의 개수는 (distinct elements의 개수가 "최대" K개인 경우의 수) - (distinct elements의 개수가 "최대" K - 1개인 경우의 수)와 같다. 따라서 이를 구현하여 답안을 도출해낼 수 있다.

import java.util.*;

/**
 * @return the number of "good subarrays" // good array : an array where the
 *         number of different integers in that array is exactly k
 */
class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return (int) (subarraysWithAtMostK(nums, k) - subarraysWithAtMostK(nums, k - 1));
    }

    public long subarraysWithAtMostK(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int right = 0;
        long ans = 0;

        while (right < nums.length) {
            map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
            while (map.size() > k) {
                map.put(nums[left], map.get(nums[left]) - 1);
                if (map.get(nums[left]) == 0) {
                    map.remove(nums[left]);
                }
                left++;
            }
            ans += right - left + 1; // the length of the subarray equals the number of subarray of each case
            right++;
        }
        return ans;
    }
}