<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 calcPairs(self, n: int) -> int:
        return n * (n - 1) / 2

    def countGood(self, nums: List[int], k: int) -> int:
        # goodness keeps track of the counts of each value
        # in the current window
        goodness = {}
        pair_ct = 0
        good_subarrays_ct = 0
        # we will use a sliding window to hunt for goodness; this
        # only needs O(n) time!!
        idx_left = 0 # about to drop
        idx_right = 1 # about to add
        goodness[nums[idx_left]] = 1
        while idx_right <= len(nums):
            if pair_ct >= k:
                #print("{}-{} is good, adding {}".format(idx_left, idx_right - 1, len(nums) - idx_right + 1))
                good_subarrays_ct += len(nums) - idx_right + 1
                # when the array is known to be good, move the left end until
                # it's no longer good or left catches up to right
                pair_ct -= self.calcPairs(goodness[nums[idx_left]])
                goodness[nums[idx_left]] -= 1
                pair_ct += self.calcPairs(goodness[nums[idx_left]])
                idx_left += 1
                if idx_left >= idx_right:
                    idx_right = idx_left + 1
            else:
                #print("{} is not good".format(goodness))
                if idx_right < len(nums):
                    # when the array is not yet good, consume the element at right
                    # and increment right
                    if nums[idx_right] in goodness:
                        pair_ct -= self.calcPairs(goodness[nums[idx_right]])
                    goodness[nums[idx_right]] = goodness.get(nums[idx_right], 0) + 1
                    pair_ct += self.calcPairs(goodness[nums[idx_right]])
                idx_right += 1
        return good_subarrays_ct
641