aboutsummaryrefslogtreecommitdiff
path: root/count_num_good_subarr.c
diff options
context:
space:
mode:
Diffstat (limited to 'count_num_good_subarr.c')
-rw-r--r--count_num_good_subarr.c94
1 files changed, 94 insertions, 0 deletions
diff --git a/count_num_good_subarr.c b/count_num_good_subarr.c
new file mode 100644
index 0000000..40c20c4
--- /dev/null
+++ b/count_num_good_subarr.c
@@ -0,0 +1,94 @@
+// 2537. Count the Number of Good Subarrays
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' and an integer 'k', return the number of good
+ * subarrays of 'nums'. a subarray 'arr' is good if 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.
+ */
+
+struct hash {
+ int *key;
+ int *val;
+ int size;
+};
+
+bool is_prime(int n) {
+ for (int i = 2; i < (int)sqrt(n) + 1; i++)
+ if (!(n % i))
+ return false;
+ return true;
+}
+
+struct hash *hash_init(int size) {
+ int max;
+ if (size < 8)
+ max = 11;
+ else {
+ max = size * 4 / 3;
+ int remove = (max - 3) % 4;
+ max += (remove > 0) * (4 - remove);
+ while (!is_prime(max))
+ max += 4;
+ }
+ struct hash *new = (struct hash *)malloc(sizeof(struct hash));
+ *new = (struct hash){(int *)calloc(max, sizeof(int)),
+ (int *)calloc(max, sizeof(int)), max};
+ return new;
+}
+
+void hash_free(struct hash *obj) {
+ free(obj->key);
+ free(obj->val);
+ free(obj);
+}
+
+int hash_getidx(struct hash *obj, int key) {
+ int idx = key % obj->size;
+ while (obj->key[idx] > 0 && obj->key[idx] != key)
+ if (++idx == obj->size)
+ idx = 0;
+ obj->key[idx] = key;
+ return idx;
+}
+
+int hash_getkey(struct hash *obj, int key) {
+ int idx = key % obj->size;
+ while (obj->key[idx] > 0) {
+ if (obj->key[idx] == key)
+ return idx;
+ if (++idx == obj->size)
+ idx = 0;
+ }
+ return -1;
+}
+
+int hash_addkey(struct hash *obj, int key) { return hash_getidx(obj, key); }
+
+long long countGood(int *nums, int numsSize, int k) {
+ long long ans = 0;
+ int curr = 0;
+ struct hash *map = hash_init(numsSize);
+ for (int l = 0, r = 0; r < numsSize; r++) {
+ int i = hash_getkey(map, nums[r]);
+ if (i == -1) {
+ i = hash_addkey(map, nums[r]);
+ map->val[i] = 1;
+ } else
+ curr += map->val[i]++;
+ while (curr >= k) {
+ ans += numsSize - r;
+ curr -= --map->val[hash_getidx(map, nums[l])];
+ l++;
+ }
+ }
+ hash_free(map);
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 1, 1, 1, 1}, n2[] = {3, 1, 4, 3, 2, 2, 4};
+ printf("%lld\n", countGood(n1, ARRAY_SIZE(n1), 10)); // expect: 1
+ printf("%lld\n", countGood(n2, ARRAY_SIZE(n2), 2)); // expect: 4
+}