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)
1#include <stdio.h>
2
3int subarraySum(int* nums, int numsSize, int k) {
4 int count = 0;
5 for (int start = 0; start < numsSize; start++) {
6 int sum = 0;
7 for (int end = start; end < numsSize; end++) {
8 sum += nums[end];
9 if (sum == k) count++;
10 }
11 }
12 return count;
13}
14
15int main() {
16 int nums[] = {1, 1, 1};
17 int k = 2;
18 int size = sizeof(nums)/sizeof(nums[0]);
19 printf("%d\n", subarraySum(nums, size, k));
20 return 0;
21}
22This C code implements a nested loop where the outer loop selects the start of the subarray and the inner loop expands it, calculating the sum. If the sum equals k, it increments the count. The time complexity is O(n^2), and the space complexity is 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)
1function subarraySum(nums, k) {
2 const prefixSumCount = {0: 1};
3 let count = 0, sum = 0;
4
5 for (const num of nums) {
6 sum += num;
7 if (prefixSumCount[sum - k]) {
8 count += prefixSumCount[sum - k];
9 }
10 prefixSumCount[sum] = (prefixSumCount[sum] || 0) + 1;
11 }
12
13 return count;
14}
15
16console.log(subarraySum([1, 1, 1], 2));
17JavaScript's approach employs an object to count prefix sums, offering compact key-value recognition, ensuring fast lookup and insertion behaved in constant time off an O(n) overall time complexity rate and O(n) space complexity due to memory handling requirements of said storage approach.