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)
1using System;
2
3public class Solution {
4 public int SubarraySum(int[] nums, int k) {
5 int count = 0;
6 for (int start = 0; start < nums.Length; start++) {
7 int sum = 0;
8 for (int end = start; end < nums.Length; end++) {
9 sum += nums[end];
10 if (sum == k) count++;
11 }
12 }
13 return count;
14 }
15
16 public static void Main(string[] args) {
17 Solution sol = new Solution();
18 int[] nums = {1, 1, 1};
19 int k = 2;
20 Console.WriteLine(sol.SubarraySum(nums, k));
21 }
22}
23The C# solution uses nested loops to evaluate each subarray sum. If a subarray sums to k, it increments the count. Typical of brute-force approaches, it has a time complexity of O(n^2) and 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)
1import java.util.HashMap;
2
3public class Solution {
4 public int subarraySum(int[] nums, int k) {
5 HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
6 prefixSumCount.put(0, 1);
7 int count = 0, sum = 0;
8
9 for (int num : nums) {
10 sum += num;
11 count += prefixSumCount.getOrDefault(sum - k, 0);
12 prefixSumCount.put(sum, prefixSumCount.getOrDefault(sum, 0) + 1);
13 }
14
15 return count;
16 }
17
18 public static void main(String[] args) {
19 Solution sol = new Solution();
20 int[] nums = {1, 1, 1};
21 int k = 2;
22 System.out.println(sol.subarraySum(nums, k));
23 }
24}
25Java's hash map is used to store counts of prefix sums, enabling efficient subarray sum computation via running total comparison against k. This results in a time complexity of O(n) and space complexity of O(n) due to hash map storage.