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 /binary_subarr_sum.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'binary_subarr_sum.c')
-rw-r--r-- | binary_subarr_sum.c | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/binary_subarr_sum.c b/binary_subarr_sum.c new file mode 100644 index 0000000..c20bfdb --- /dev/null +++ b/binary_subarr_sum.c @@ -0,0 +1,52 @@ +// 930. Binary Subarrays With Sum +#include "leetcode.h" + +/* + * given a binary array 'nums' and an integer 'goal', return the number o + * non-empty subarrays with a sum 'goal'. a subarray is a contiguous part of the + * array + */ + +int numSubarraysWithSum(int *nums, int numsSize, int goal) { + int n = numsSize, m = n + 1, sum = 0, rm, d, ans = 0; + int **hash = calloc(m, sizeof(int *)); + hash[0] = malloc(2 * sizeof(int)); + hash[0][0] = 0; + hash[0][1] = 1; + for (int i = 0; i < n; i++) { + sum += nums[i]; + rm = sum - goal; + d = rm; + while (1 && rm >= 0) { + if (hash[d % n] == NULL) + break; + else if (hash[d % n][0] == rm) { + ans += hash[d % n][1]; + break; + } else { + d++; + } + } + d = sum; + while (1) { + if (hash[d % n] == NULL) { + hash[d % n] = malloc(2 * sizeof(int)); + hash[d % n][0] = sum; + hash[d % n][1] = 1; + break; + } else if (hash[d % n][0] == sum) { + hash[d % n][1]++; + break; + } else { + d++; + } + } + } + return ans; +} + +int main() { + int n1[] = {1, 0, 1, 0, 1}, n2[] = {0, 0, 0, 0, 0}; + printf("%d\n", numSubarraysWithSum(n1, ARRAY_SIZE(n1), 2)); // expect: 4 + printf("%d\n", numSubarraysWithSum(n2, ARRAY_SIZE(n2), 0)); // expect: 15 +} |