You are given an array nums consisting of positive integers.
We call a subarray of an array complete if the following condition is satisfied:
Return the number of complete subarrays.
A subarray is a contiguous non-empty part of an array.
Example 1:
Input: nums = [1,3,1,2,2] Output: 4 Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].
Example 2:
Input: nums = [5,5,5,5] Output: 10 Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 2000class Solution {
public int countCompleteSubarrays(int[] nums) {
HashMap<Integer, Integer> set = new HashMap<>();
int n = nums.length, count = 0;
for (int i = 0; i < n; i++)
set.put(nums[i], 1);
int distinct = set.size();
set.clear();
for (int lt = 0, rt = 0; lt < n; lt++) {
if (lt > 0) {
int front = nums[lt - 1];
set.put(front, set.get(front) - 1);
if (set.get(front) == 0)
set.remove(front);
}
while (rt < n && set.size() < distinct){
set.put(nums[rt], set.getOrDefault(nums[rt], 0) + 1);
rt++;
}
// System.out.println(set);
if (set.size() == distinct)
count += n - (rt - 1);
}
return count;
}
}