Count the Number of Good Subarrays[M,Array,Hash Table,Sliding Window]

https://leetcode.com/problems/count-the-number-of-good-subarrays/description/

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

A subarray arr is good if it there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

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

 

Example 1:

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: The only good subarray is the array nums itself.

Example 2:

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 109

1.C++

줘낸 어렵다.. 일단 C++은 gg

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        long long count = 0;
        long long ret = 0;
        int n = nums.size();
        int j = 0;
        for(int i=0; i<n; i++) {
            int num = nums[i];
            count += freq[num];
            freq[num]++;
            while(count >= k && j<=i ) {
                // n - i is the number of sub array 
                // [j...i] is alreay a valid subarray, so
                // [j...i, i+1], [j...i, i+1, i+2], ... [j..i, i+1, i+2, ...n-1] is alo valid sub arrray
                // the number of sub arrays are n-i
                ret += (n - i);
                num = nums[j];
                freq[num]--;
                count -= freq[num];
                j++;
            }
            
        }
        return ret;
    }
};

 

풀어서 쓰면 이런 느낌

 

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        long long count = 0;
        long long ret = 0;
        int n = nums.size();
        int j = 0;
        for(int i=0; i<n; i++) {
            int num = nums[i];
            count += freq[num];
            freq[num]++;
            while(count >= k && j<=i ) {
                // n - i is the number of sub array 
                // [j...i] is alreay a valid subarray, so
                // [j...i, i+1], [j...i, i+1, i+2], ... [j..i, i+1, i+2, ...n-1] is alo valid sub arrray
                // the number of sub arrays are n-i
                ret += (n - i);
                num = nums[j];
                freq[num]--;
                count -= freq[num];
                j++;
            }
            
        }
        return ret;
    }
};

 

솔직히 이건 뭐.. 봐도 모르겄다.

깜냥에 맞는 문제를 풀어야겠다.

 

할만 한 줄 알았는데 알고보면 안 할만한 경우가 허다하다 허다해

 

2. Python

2 pointer를 이용한 파이썬 풀이도 알아보자

 

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        left = 0
        ans = 0
        tally = 0
        n = len(nums)
        d = defaultdict(int)

        for right,num in enumerate(nums):
            tally += d[num]
            d[num] += 1

            while tally >= k :
                ans += n - right
                d[nums[left]] -= 1
                tally -= d[nums[left]]
                left += 1
        return ans

 

defaultdict라는 특이한 python 만의 data구조를 이용한다.

 

In Python, defaultdict is a subclass of the built-in dict class provided by the collections module. It is used to create dictionaries with default values for missing keys automatically. This means if you try to access or modify a key that does not exist in the dictionary, defaultdict will automatically create the key with a default value instead of raising a KeyError.

The syntax for defaultdict is:

python

 

from collections import defaultdict d = defaultdict(default_factory)

Here, default_factory is a function that provides the default value for missing keys. Commonly used default_factory functions are int, list, set, etc.

For example:

python

 

from collections import defaultdict # defaultdict with int will default missing keys to 0 d = defaultdict(int) d['a'] += 1 # 'a' is not in d, so it initializes d['a'] with 0 and then adds 1 print(d) # Output: defaultdict(<class 'int'>, {'a': 1})

In your code:

python

 

n, d = len(nums), defaultdict(int)

defaultdict(int) initializes the dictionary d such that if a key does not exist, it will default to 0. This is particularly useful in your code to keep track of counts without having to check if the key exists every time you increment or decrement the count.