Question 26 : Find subarrays with given sum in an array.

Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Subarrays having their sum equal to the given integer.
For example :

Input :
Input-int[] arr = {2, 3, 6, 4, 9, 0, 11};
int num = 9
Output-
starting index : 1, Ending index : 2
starting index : 5, Ending index : 5
starting index : 5, Ending index : 6

Explanation :
[3, 6] [9],
[9,0] These all are the subarrays with their sum equal to 9

Solution 1. Brute Force (Nested Loops)

public class SubarraySumBrute {

    public static int countSubarrays(int[] arr, int target) {
        int count = 0;
        int n = arr.length;

        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == target) {
                    count++;
                }
            }
        }
        return count;
    }
}

Python

def count_subarrays_brute(arr, target):
    count = 0
    n = len(arr)

    for i in range(n):
        s = 0
        for j in range(i, n):
            s += arr[j]
            if s == target:
                count += 1
    return count

Solution 2.Sliding window (only non-negatives)

We can solve this problem in linear time i.e. in O(n) as the worst time complexity.

We can maintain two pointers, start and end pointers which basically represents a subarray and also we have to take a variable which stores the current sum of the subarray starting from start pointer and ending at end pointer.

•  we keep on incrementing end pointer while adding the element in the current sum until we reach a point where our current running sum is more than required target sum, this basically means that the current subarray whose sum we’ve calculated is not the right answer.
• So now we alter our subarray by moving the start pointer, that is shortening the subarray and hence the current sum in the hope that we achieve the current sum equal to the required target sum.
• At every point we check if our current sum is equal to target sum or not, if this is the case we print our pointers.
• So basically we are altering the subarray by increasing start and end pointers and changing the current sum depending on its value as compared to target sum.

public class SubarraySumSliding {

    public static int countSubarrays(int[] arr, int target) {
        int left = 0, sum = 0, count = 0;

        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];

            while (sum > target && left <= right) {
                sum -= arr[left++];
            }

            if (sum == target) {
                count++;
            }
        }
        return count;
    }
}

Python 

def count_subarrays_sliding(arr, target):
    left = 0
    total = 0
    count = 0

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

        while total > target and left <= right:
            total -= arr[left]
            left += 1

        if total == target:
            count += 1

    return count

Solution 3 Prefix Sum + HashMap (Best General Solution)

arr = [1, 2, 1, 2, 1]
target = 3


Index
 Num
 Prefix_Sum
Map (prefix → count)
Start
 — 
 0
      {0:1}
0
 1
 1
      {0:1, 1:1}
1 
 2
 3
      {0:1, 1:1, 3:1}
2
 1
 4
      {0:1, 1:1, 3:1, 4:1}
3
 2
 6
      {0:1, 1:1, 3:1, 4:1, 6:1}
4
 1
 7
      {0:1, 1:1, 3:1, 4:1, 6:1, 7:1}

import java.util.HashMap;
import java.util.Map;

public class SubarraySumPrefix {

    public static int countSubarrays(int[] arr, int target) {
        int prefix = 0;
        int count = 0;

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        for (int num : arr) {
            prefix += num;

            if (map.containsKey(prefix - target)) {
                count += map.get(prefix - target);
            }

            map.put(prefix, map.getOrDefault(prefix, 0) + 1);
        }

        return count;
    }
}

Python 
def count_subarrays_prefix(arr, target):
    prefix = 0
    count = 0
    freq = {0: 1}

    for num in arr:
        prefix += num
        if prefix - target in freq:
            count += freq[prefix - target]
        freq[prefix] = freq.get(prefix, 0) + 1

    return count




  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      HashMap prefix sums
    
    

      O(n)
    
    

      O(n)
    
    

      ⭐ Works with negative numbers
    
  

  

    

      Sliding window (only non-negatives)
    
    

      O(n)
    
    

      O(1)
    
    

      Works if all values ≥ 0
    
  

  

    

      Brute force nested loops
    
    

      O(n²)
    
    

      O(1)
    
    

      ❌ Inefficient