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

Problem :

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

Solution:

Solution 1:

Check all sub arrays and if current sum is equal to X, return. This will require two loops and if currentSum is greater than X tben try another sub array.
Java code:

static void findSubArraySumEqualToX(int arr[], int X) {
 int currentSum;
 for (int i = 0; i < arr.length; i++) {
 currentSum = arr[i];
 // try all subarrays starting with 'i'
 for (int j = i + 1; j <= arr.length; j++) {
 if (currentSum == X) {
 int endIndexForContArray = j - 1;
 System.out.println("Sum found between indexes " + i + " and " + endIndexForContArray);
 for (int k = i; k <= endIndexForContArray; k++) {
 System.out.print(arr[k]+" ");
 }
 return;
 }
 if (currentSum > X || j == arr.length)
 break;
 currentSum = currentSum + arr[j];
 }
 }

 System.out.println("No subarray found");
 return;
 }

Time Complexity : O(N^2)

Solution 2: 

Lets say array is arr[] and given sum is X.

• Iterate over array arr[].
• If currentSum is less than X then add current element to currentSum.
• If currentSum is greater than X , it means we need to remove starting elements to make currentSum less than X.
• If CurrentSum is equal to X, we got the continuous sub array, print it.

 public static void findSubArraySumEqualToXOptimized(int arr[], int X) {
  int currentSum = arr[0];
  int start = 0;

  for (int i = 1; i <= arr.length; i++) {
   // If currentSum is more than the sum, start removing starting elements unless you get currentSum is less than X
   while (currentSum > X && start < i - 1) {
    currentSum = currentSum - arr[start];
    start++;
   }

   // If currentSum becomes equal to sum, then print the index
   if (currentSum == X) {
    int endIndexForContArray = i - 1;
    System.out.println("Sum found between indexes " + start + " and " + endIndexForContArray);
    System.out.println("Printing Array values : ");
    for (int j = start; j <= endIndexForContArray; j++) {
     System.out.print(arr[j]+" ");
    }
    return;
   }

   // Add this element to currentSum
   if (i < arr.length)
    currentSum = currentSum + arr[i];
  }

Time Complexity : O(N) 

Java program to find the Contiguous Subarray with Sum to a Given Value in an array :

package org.arpit.java2blog;

public class FindSumSubArrayMain {
 public static void main(String[] args) {

  int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };

     findSubArraySumEqualToX(arr, 33);
     System.out.println("n======================");
  findSubArraySumEqualToXOptimized(arr, 33);
 }

 static void findSubArraySumEqualToX(int arr[], int X) {
  int currentSum;
  for (int i = 0; i < arr.length; i++) {
   currentSum = arr[i];
   // try all subarrays starting with 'i'
   for (int j = i + 1; j <= arr.length; j++) {
    if (currentSum == X) {
     int endIndexForContArray = j - 1;
     System.out.println("Sum found between indexes " + i + " and " + endIndexForContArray);
     for (int k = i; k <= endIndexForContArray; k++) {
      System.out.print(arr[k]+" ");
     }
     return;
    }
    if (currentSum > X || j == arr.length)
     break;
    currentSum = currentSum + arr[j];
   }
  }

  System.out.println("No subarray found");
  return;
 }

 public static void findSubArraySumEqualToXOptimized(int arr[], int X) {
  int currentSum = arr[0];
  int start = 0;

  for (int i = 1; i <= arr.length; i++) {
   // If currentSum is more than the sum, start removing starting elements unless you get currentSum is less than X
   while (currentSum > X && start < i - 1) {
    currentSum = currentSum - arr[start];
    start++;
   }

   // If currentSum becomes equal to sum, then print the index
   if (currentSum == X) {
    int endIndexForContArray = i - 1;
    System.out.println("Sum found between indexes " + start + " and " + endIndexForContArray);
    System.out.println("Printing Array values : ");
    for (int j = start; j <= endIndexForContArray; j++) {
     System.out.print(arr[j]+" ");
    }
    return;
   }

   // Add this element to currentSum
   if (i < arr.length)
    currentSum = currentSum + arr[i];
  }

 }

}

When you run above program , you will get below output:

Sum found between indexes 6 and 7
10 23 
======================
Sum found between indexes 6 and 7
Printing Array values : 
10 23