diff options
-rw-r--r-- | count_complete_subarr_arr.c | 50 | ||||
-rw-r--r-- | count_complete_subarr_arr.py | 35 |
2 files changed, 85 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 +} diff --git a/count_complete_subarr_arr.py b/count_complete_subarr_arr.py new file mode 100644 index 0000000..ca0371d --- /dev/null +++ b/count_complete_subarr_arr.py @@ -0,0 +1,35 @@ +# 2799. Count Complete Subarrays in an Array +from collections import Counter + +""" +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. +""" + + +class Solution(object): + def countCompleteSubarrays(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n, k, i = len(nums), len(set(nums)), 0 + ans, cnt = 0, Counter() + for j in range(n): + cnt[nums[j]] += 1 + while len(cnt) == k: + cnt[nums[i]] -= 1 + if cnt[nums[i]] == 0: + del cnt[nums[i]] + i += 1 + ans += i + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countCompleteSubarrays(nums=[1, 3, 1, 2, 2])) + print(obj.countCompleteSubarrays(nums=[5, 5, 5, 5])) |