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)
1public class Solution {
2 public int subarraySum(int[] nums, int k) {
3 int count = 0;
4 for (int start = 0; start < nums.length; start++) {
5 int sum = 0;
6 for (int end = start; end < nums.length; end++) {
7 sum += nums[end];
8 if (sum == k) count++;
9 }
10 }
11 return count;
12 }
13
14 public static void main(String[] args) {
15 Solution sol = new Solution();
16 int[] nums = {1, 1, 1};
17 int k = 2;
18 System.out.println(sol.subarraySum(nums, k));
19 }
20}
21The Java solution uses nested loops to explore all subarrays and calculate their sums. If the sum equals k, it increments the count variable. This approach maintains O(n^2) time complexity and 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)
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5int subarraySum(std::vector<int>& nums, int k) {
6 std::unordered_map<int, int> prefixSumCount;
7 prefixSumCount[0] = 1;
8 int count = 0, sum = 0;
9
10 for (int num : nums) {
11 sum += num;
12 count += prefixSumCount[sum - k];
13 prefixSumCount[sum]++;
14 }
15
16 return count;
17}
18
19int main() {
20 std::vector<int> nums = {1, 1, 1};
21 int k = 2;
22 std::cout << subarraySum(nums, k) << std::endl;
23 return 0;
24}
25The C++ solution employs an unordered_map for efficient prefix sum tracking. By adjusting the count with the difference of the current sum and k, it quickly identifies subarrays meeting the condition. Time complexity is O(n) and space complexity is O(n).