Python Program to Count Subarray with given Sum.

Input: arr = [1, 2, 3, 2, 1] sum = 3
Output: Number of Subarrays: 3

Explanation:
There are 3 subarrays sum up to the target sum of 3:
[1, 2]
[3]
[2, 1]

• Use two nested loops to generate all possible subarrays.
• Calculate the sum of each subarray.
• Count the number of subarrays with the given sum.

# Python code to count subarrays for given sum (Brute Force)
def count_subarrays(arr, target_sum):
    count = 0
    n = len(arr)
    
    for start in range(n):
        current_sum = 0
        for end in range(start, n):
            current_sum += arr[end]
            if current_sum == target_sum:
                count += 1
    
    return count

arr = [1, 2, 3, 2, 1]
sum = 3
print("Number of Subarrays:", count_subarrays(arr, sum))

Number of Subarrays: 3

• Time Complexity: As we are checking for all possible subarrays using a nested loop the time complexity of this approach is O(n^2) where n is the length of the array.

• Space Complexity: We are not using any extra space in this approach so the space complexity is O(1).

• Calculate the cumulative sum of the array elements.
• Maintain a hash map to store the cumulative sums and their frequencies.
• Determine the count of subarrays with the given sum using the hash map.

# Python code to count subarray for given sum using prefix sum
def count_subarrays(arr, target_sum):
    count = 0
    prefix_sum = {0: 1}
    current_sum = 0
    
    for num in arr:
        current_sum += num
        if current_sum - target_sum in prefix_sum:
            count += prefix_sum[current_sum - target_sum]
        
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    
    return count

arr = [1, 4, 20, 3, 10, 5]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))

• Use two pointers, typically named left and right, to represent the window boundaries.
• Initialize left and right to the start of the array.
• Expand the window by moving the right pointer to the right.
• Adjust the window based on the current sum.
• If the current sum exceeds the desired sum or target sum, shrink the window by moving the left pointer to the right.
• Continue this process until the sum becomes less than or equal to the target sum.
• Whenever the current sum matches the desired sum, increment the count to track the subarrays that satisfy the condition.
• Continue sliding the window until the right pointer reaches the end of the array.

# Python code count subarrays using sliding window algorithm
def count_subarrays(arr, target_sum):
    count = 0
    current_sum = 0
    left = 0

    for right in range(len(arr)):
        current_sum += arr[right]

        while current_sum > target_sum and left <= right:
            current_sum -= arr[left]
            left += 1

        if current_sum == target_sum:
            count += 1

    return count

arr = [1, 4, 20, 3, 10, 5, 15]
sum = 33
print("Number of Subarrays:", count_subarrays(arr, sum))