Subarray Sum Equals K

Array, Hash Table

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• 1 <= nums.length <= 2 * 104

• -1000 <= nums[i] <= 1000

• -107 <= k <= 107

Solutions

Approach - Brute Force Technique

Steps

1. Initialize Counter: The algorithm starts by initializing a counter count to 0. This will keep track of the number of subarrays that sum to k.

2. Iterate Over Array: The algorithm then enters a nested loop that iterates over each possible subarray in nums.

   • Calculate Subarray Sum: For each subarray, the algorithm calculates the sum of the elements in the subarray.

   • Check for Desired Sum: If the sum of the elements in the subarray equals k, the algorithm increments count.

3. Return Result: After the loops, the algorithm returns count, which is the total number of continuous subarrays whose sum equals to k.

public class Solution {
    public int SubarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.Length; start++) {
            int sum=0;
            for (int end = start; end < nums.Length; end++) {
                sum+=nums[end];
                if (sum == k)
                    count++;
            }
        }
        return count;
    }
}

Complexity

• Time complexity: O(N^2)

• Space complexity: O(1)

Approach - Hash Table Technique

Steps

1. Initialize Variables: The algorithm starts by initializing a dictionary prefix to keep track of cumulative sums and their counts, an integer sum to keep track of the cumulative sum, and an integer ret to keep track of the number of subarrays that sum to k.

2. Handle Base Case: The algorithm adds an entry to the prefix dictionary for a sum of zero with a count of one. This represents the sum of no elements.

3. Iterate Over Array: The algorithm then enters a loop that iterates over each element in the input array nums.

   • Update Cumulative Sum: For each element, the algorithm adds the element’s value to sum.

   • Check for Subarray Sum: The algorithm calculates the value find as the difference between the current cumulative sum and k. If find is in the prefix dictionary, it means that there is a subarray ending at the current index with a sum of k. The algorithm increments ret by the count of find in prefix.

   • Update Prefix Dictionary: The algorithm then checks if the current cumulative sum is in the prefix dictionary. If it is, the count is incremented; otherwise, a new entry is added with a count of one.

4. Return Result: After the loop, the algorithm returns ret, which is the total number of continuous subarrays whose sum equals to k.

public class Solution {
    public int SubarraySum(int[] nums, int k) {

        Dictionary<int, int> prefix = new Dictionary<int, int>();
        int sum = 0;
        int ret = 0;
        prefix[0] = 1; // we always have 1 sum of zero, which is sum of none.
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];

            int find = sum - k;
            if (prefix.ContainsKey(find))
            {
                ret += prefix[find];
            }
            if (prefix.ContainsKey(sum))
            {
                prefix[sum]++;
               
            }
            else
            {
                
                prefix.Add(sum, 1);
            }
            
        }
        return ret; 
    }
}

Complexity

• Time complexity: O(N)

• Space complexity: O(N)