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 <iostream>
2#include <vector>
3
4int subarraySum(std::vector<int>& nums, int k) {
5 int count = 0;
6 for (size_t start = 0; start < nums.size(); ++start) {
7 int sum = 0;
8 for (size_t end = start; end < nums.size(); ++end) {
9 sum += nums[end];
10 if (sum == k) ++count;
11 }
12 }
13 return count;
14}
15
16int main() {
17 std::vector<int> nums = {1, 1, 1};
18 int k = 2;
19 std::cout << subarraySum(nums, k) << std::endl;
20 return 0;
21}
22The C++ code functions similarly to the C code, using nested loops to check sums of all subarrays, incrementing the count whenever the sum equals k. This straightforward approach results in O(n^2) time complexity, with O(1) space complexity.
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)
1from collections import defaultdict
2
3def subarray_sum(nums, k):
4 prefix_sum_count = defaultdict(int)
5 prefix_sum_count[0] = 1
6 count = sum_ = 0
7
8 for num in nums:
9 sum_ += num
10 count += prefix_sum_count[sum_ - k]
11 prefix_sum_count[sum_] += 1
12
13 return count
14
15# Example usage
16nums = [1, 1, 1]
17k = 2
18print(subarray_sum(nums, k))
19This Python solution utilizes a defaultdict to store prefix sums counts, allowing for dynamic and efficient querying of existing sums and direct summation of subarray occurrences satisfying the sum condition. The time and space complexities are O(n).