Question 38 : Find the Contiguous Subarray with Sum to a Given Value in an array

Given an array of positive integer and given value X, find Contiguous sub array whose sum is equal to X.
For example :

arr[]={14, 12, 70, 15, 99, 65, 21, 90};
X =97.
Sum found between index 1 to 3
Elements are 12, 17 and 15

Java — Sliding Window

public class SubarraySumNonNegative {

    public static int[] findSubarray(int[] arr, int target) {
        int start = 0;
        int sum   = 0;

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

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

            if (sum == target) {
                return new int[]{start, end};
            }
        }

        return new int[]{-1, -1}; // not found
    }
}

Python:

def find_subarray_nonneg(arr, target):
    start = 0
    sum_ = 0

    for end in range(len(arr)):
        sum_ += arr[end]
        while sum_ > target and start < end:
            sum_ -= arr[start]
            start += 1
        if sum_ == target:
            return (start, end)

    return (-1, -1)

Prefix Sum + HashMap (Handles Negatives)

import java.util.*;

public class SubarraySumGeneral {

    public static int[] findSubarray(int[] arr, int target) {
        Map<Integer, Integer> prefixMap = new HashMap<>();
        prefixMap.put(0, -1); // handle sum from start

        int prefix = 0;

        for (int i = 0; i < arr.length; i++) {
            prefix += arr[i];

            if (prefixMap.containsKey(prefix - target)) {
                int start = prefixMap.get(prefix - target) + 1;
                return new int[]{start, i};
            }

            prefixMap.putIfAbsent(prefix, i);
        }

        return new int[]{-1, -1};
    }
}

Python 

def find_subarray_general(arr, target):
    prefix_map = {0: -1}
    prefix = 0

    for i, num in enumerate(arr):
        prefix += num
        if prefix - target in prefix_map:
            return (prefix_map[prefix - target] + 1, i)
        if prefix not in prefix_map:
            prefix_map[prefix] = i

    return (-1, -1)

Brute Force (All Subarrays)
public class SubarraySumBrute {

    public static int[] findSubarray(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                if (sum == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{-1, -1};
    }
}

Python 
def find_subarray_brute(arr, target):
    n = len(arr)
    for i in range(n):
        sum_ = 0
        for j in range(i, n):
            sum_ += arr[j]
            if sum_ == target:
                return (i, j)
    return (-1, -1)


  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      Sliding window (non-negative)
    
    

      O(n)
    
    

      O(1)
    
    

      ⭐ Best if arr ≥ 0
    
  

  

    

      Prefix sum + HashMap
    
    

      O(n)
    
    

      O(n)
    
    

      Works with negatives
    
  

  

    

      Brute force nested
    
    

      O(n²)
    
    

      O(1)
    
    

      ❌ Slow