Find Subarrays With Equal Sum - Leetcode Solution

Problem Statement:

Given an array of integers nums, return the number of non-empty subarrays that sum to target.

Example:

Input: nums = [1,1,1], target = 2 Output: 2 Explanation: Two subarrays have sum 2: [1,1] and [1,1].

Solution:

Approach:

• Keep a track of the prefix sum.
• Create an empty hash table. The key of the hash table would be the prefix sum and the value would be the count of prefix sum you have at every position.
• Calculate the prefix sum of every number in the given list.
• Check if the prefix sum is equal to the target sum. If yes, increase the count by one.
• Check if the prefix sum is already present in the hash table. If yes, add the count of the prefix sum in the hash table by 1, if no add the prefix sum and its count to the hash table.
• If the difference between the current prefix sum and target sum is already present in the hash table, increment the answer by the count of the difference in the hash table.

Algorithm:

• Initialize prefix_sum and counter = 0
• Initialize empty hash table prefix_sum_table = {}
• Loop through each element in the list i.e. nums:
  • Add the current element to the prefix_sum.
  • If prefix_sum is equal to target:
    • Increment counter by 1.
  • If prefix_sum - target is present in the prefix_sum_table:
    • Increment counter by the value of prefix_sum_table[prefix_sum-target]
  • Add prefix_sum to prefix_sum_table if it is not already present with a value of 1.
  • If prefix_sum is already present in prefix_sum_table:
    • Increment the value of prefix_sum by 1.
• Return counter

Code:

def findSubarraysWithEqualSum(nums, target): prefix_sum = 0 prefix_sum_table = {} counter = 0

for i in range(len(nums)):
    prefix_sum += nums[i]

    if prefix_sum == target:
        counter += 1

    if (prefix_sum - target) in prefix_sum_table:
        counter += prefix_sum_table[prefix_sum-target]

    if prefix_sum in prefix_sum_table:
        prefix_sum_table[prefix_sum] += 1
    else:
        prefix_sum_table[prefix_sum] = 1

return counter

Time Complexity:

The time complexity of the above solution is O(n) where n is the length of the nums list.

1