<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>good</strong> subarrays of</em> <code>nums</code>.</p>

<p>A subarray <code>arr</code> is <strong>good</strong> if it there are <strong>at least </strong><code>k</code> pairs of indices <code>(i, j)</code> such that <code>i &lt; j</code> and <code>arr[i] == arr[j]</code>.</p>

<p>A <strong>subarray</strong> is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,1,4,3,2,2,4], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        # use hashmap to record the count of each number in the subarry
        result = 0
        hmap = {}
        # j .. i
        j = 0
        countPairs = 0
        for i in range(0, len(nums)):
            # print(i)
            # add i to hmap
            hmap[nums[i]] = hmap.get(nums[i], 0) + 1
            c = hmap[nums[i]]
            countPairs = countPairs + c*(c-1)/2 - (c-1)*(c-2)/2
            # print(hmap)
            while countPairs >= k:
                result += len(nums)-i
                # remove j from hmap
                c = hmap[nums[j]]
                countPairs = countPairs - c*(c-1)/2 + (c-1)*(c-2)/2
                hmap[nums[j]] -= 1
                
                j += 1
            
        return result

    # def good(self, hmap: dict[int, int], k) -> bool:
    #     _sum = 0
    #     for _, count in hmap.items():
    #         if count >= 2:
    #             _sum += (count-1)*count/2
    #     return _sum >= k

        
578