diff options
Diffstat (limited to 'count_complete_subarr_arr.c')
-rw-r--r-- | count_complete_subarr_arr.c | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/count_complete_subarr_arr.c b/count_complete_subarr_arr.c new file mode 100644 index 0000000..bd16ad4 --- /dev/null +++ b/count_complete_subarr_arr.c @@ -0,0 +1,50 @@ +// 2799. Count Complete Subarrays in an Array +#include "leetcode.h" + +/* + * you are given an array 'nums' consisting of positive integers. we call a + * subarray of an array complete if the following condition is satisfied. the + * number of distinct elements in the subarray is equal to the number of + * distinct elements in the whole array. return the number of complete + * subarrays. a subarray is a contiguous non-empty part of an array. + */ + +int countCompleteSubarrays(int *nums, int numsSize) { + int elem[2001] = {0}, distinct = 0, ans = 0; + for (int i = 0; i < numsSize; i++) { + if (!elem[nums[i]]) + distinct++; + elem[nums[i]]++; + } + int low = 0, high = 0, curr = 0; + memset(elem, 0, sizeof(elem)); + while (curr < distinct) { + if (!elem[nums[high]]) + curr++; + elem[nums[high]]++; + high++; + } + ans += numsSize - high + 1; + while (low < numsSize) { + elem[nums[low]]--; + if (!elem[nums[low]]) + curr--; + while (high < numsSize && curr < distinct) { + if (!elem[nums[high]]) + curr++; + elem[nums[high]]++; + high++; + } + if (curr < distinct) + break; + ans += numsSize - high + 1; + low++; + } + return ans; +} + +int main() { + int n1[] = {1, 3, 1, 2, 2}, n2[] = {5, 5, 5, 5}; + printf("%d\n", countCompleteSubarrays(n1, ARRAY_SIZE(n1))); // expect: 4 + printf("%d\n", countCompleteSubarrays(n2, ARRAY_SIZE(n2))); // expect: 10 +} |