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)
1def subarray_sum(nums, k):
2 count = 0
3 for start in range(len(nums)):
4 total = 0
5 for end in range(start, len(nums)):
6 total += nums[end]
7 if total == k:
8 count += 1
9 return count
10
11# Example usage
12nums = [1, 1, 1]
13k = 2
14print(subarray_sum(nums, k))
15This Python solution adopts a two-loop system to find subarrays whose sums equal k. The outer loop sets the starting index, while the inner loop calculates the sum. This approach yields 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)
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int SubarraySum(int[] nums, int k) {
6 var prefixSumCount = new Dictionary<int, int>();
7 prefixSumCount[0] = 1;
8 int count = 0, sum = 0;
9
10 foreach (int num in nums) {
11 sum += num;
12 if (prefixSumCount.TryGetValue(sum - k, out int prefixSumOccurrences)) {
13 count += prefixSumOccurrences;
14 }
15 if (!prefixSumCount.ContainsKey(sum))
16 prefixSumCount[sum] = 0;
17 prefixSumCount[sum]++;
18 }
19
20 return count;
21 }
22
23 public static void Main(string[] args) {
24 Solution sol = new Solution();
25 int[] nums = {1, 1, 1};
26 int k = 2;
27 Console.WriteLine(sol.SubarraySum(nums, k));
28 }
29}
30This C# solution utilizes a Dictionary to efficiently handle prefix sum frequencies, facilitating quick determination of count increments whenever k is achieved through this summation method. This brings a time complexity of O(n) and necessitates space usage of O(n) for storage.