2537. Count the Number of Good Subarrays

Problem

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

Solution (Java)

class Solution {
    public long countGood(int[] nums, int k) {
        int j=0;
        int i=0;
        long ans=0l;
        long count=0l;
        HashMap<Integer,Integer> hm=new HashMap<>();
        while(j<nums.length){
            hm.put(nums[j],hm.getOrDefault(nums[j],0)+1);
            count += hm.get(nums[j]) - 1;
            while(count>=k){
                ans += (nums.length - j);
                int lf = hm.get(nums[i]);
                count-=lf-1;
                hm.put(nums[i], hm.get(nums[i]) - 1);
                if(hm.get(nums[i])==0)
                    hm.remove(nums[i]);              
                i++;
            }
            j++;
        }
        return ans;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).