This straightforward approach involves checking all possible subarrays in the given array. We calculate the sum for each subarray and check if it equals k. Although simple, it can be inefficient for large arrays due to its O(n^2) time complexity.
Time Complexity: O(n^2)
Space Complexity: O(1)
1function subarraySum(nums, k) {
2 let count = 0;
3 for (let start = 0; start < nums.length; start++) {
4 let sum = 0;
5 for (let end = start; end < nums.length; end++) {
6 sum += nums[end];
7 if (sum === k) count++;
8 }
9 }
10 return count;
11}
12
13console.log(subarraySum([1, 1, 1], 2));
14JavaScript likewise iterates through the array with double loops to identify subarrays summing to k. It results in a time complexity of O(n^2) and a space complexity of O(1).
This optimized approach uses a hashmap to store prefix sums, facilitating the identification of subarrays with the desired sum in constant time. By keeping a count of prefix sums that have been seen, we can determine how many times a specific sum - k has appeared, suggesting that a subarray ending at the current position sums to k.
Time Complexity: O(n)
Space Complexity: O(n)
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int subarraySum(int* nums, int numsSize, int k) {
6 int count = 0, sum = 0, i;
7 int *prefixSumCount = calloc(20000, sizeof(int));
8 int offset = 10000;
9 prefixSumCount[offset] = 1;
10
11 for (i = 0; i < numsSize; i++) {
12 sum += nums[i];
13 int target = sum - k;
14 count += prefixSumCount[target + offset];
15 prefixSumCount[sum + offset]++;
16 }
17
18 free(prefixSumCount);
19 return count;
20}
21
22int main() {
23 int nums[] = {1, 1, 1};
24 int k = 2;
25 int size = sizeof(nums)/sizeof(nums[0]);
26 printf("%d\n", subarraySum(nums, size, k));
27 return 0;
28}
29This C implementation uses a hash table to track the occurrence of prefix sums, adjusted with an offset for negative indices safety, enabling identification of subarrays summing to k. The time complexity reduces to O(n), with space complexity also improving due to the hash table.