diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /continuous_subarr_sum.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'continuous_subarr_sum.c')
-rw-r--r-- | continuous_subarr_sum.c | 76 |
1 files changed, 76 insertions, 0 deletions
diff --git a/continuous_subarr_sum.c b/continuous_subarr_sum.c new file mode 100644 index 0000000..06879a3 --- /dev/null +++ b/continuous_subarr_sum.c @@ -0,0 +1,76 @@ +#include <limits.h> +#include <stdbool.h> +#include <stdio.h> +#include <stdlib.h> + +struct node { + int key; + int val; + struct node *next; +}; + +struct table { + int size; + struct node **list; +}; + +struct table *createTable(int size) { + struct table *t = (struct table *)malloc(sizeof(struct table)); + t->size = size; + t->list = (struct node **)malloc(sizeof(struct node *) * size); + for (int i = 0; i < size; i++) + t->list[i] = NULL; + return t; +} + +int hashCode(struct table *t, int key) { + if (key < 0) + return -(key % t->size); + return key % t->size; +} + +void insert(struct table *t, int key, int val) { + int pos = hashCode(t, key); + struct node *list = t->list[pos]; + struct node *newNode = (struct node *)malloc(sizeof(struct node)); + newNode->key = key; + newNode->val = val; + newNode->next = list; + t->list[pos] = newNode; +} + +int lut(struct table *t, int key) { + int pos = hashCode(t, key); + struct node *list = t->list[pos]; + struct node *tmp = list; + while (tmp) { + if (tmp->key == key) + return tmp->val; + tmp = tmp->next; + } + return INT_MAX; +} + +bool checkSubarraySum(int *nums, int numsSize, int k) { + struct table *t = createTable(10); + int sum = 0; + insert(t, 0, -1); + for (int i = 0; i < numsSize; i++) { + sum += nums[i]; + if (k) + sum %= k; + if (lut(t, sum) != INT_MAX) { + if (i - lut(t, sum) > 1) + return true; + } else + insert(t, sum, i); + } + return false; +} + +int main() { + int nums1[] = {23, 2, 4, 6, 7}, nums2[] = {23, 2, 6, 4, 7}; + printf("%d\n", checkSubarraySum(nums1, 5, 6)); // expect: 1 + printf("%d\n", checkSubarraySum(nums2, 5, 6)); // expect: 1 + printf("%d\n", checkSubarraySum(nums2, 5, 13)); // expect: 0 +} |