Sub Array with Given Sum in Java

Sub Array with Given Sum In Java Programming

In Sub array with given sum in java article, we will explore how to write a Java program that finds all sub arrays within a given array whose elements sum up to a specific target value. The input consists of an array of non negative integers and a target number. Our task is to identify and print all pairs of starting and ending indices for the sub arrays whose sum matches the given number. 

This problem is a common one in coding interviews and algorithm challenges, as it helps in understanding concepts related to arrays, sliding window techniques, and efficient iteration. 

We will walk through the problem statement, discuss the underlying logic and approach, and finally implement a complete solution using Java.

Sub array with given sum in Java Programming

Sub Array With Given Sum in Java

Sub Array With Given Sum in Java

Sub array with a given sum in Java is a program that helps find a group of numbers that are next to each other in an array and add up to a specific number. In other words, the program looks for a sequence of continuous elements in the array whose total is equal to the number you are looking for.

Example:

Let’s say the array is:

 arr[] = {1, 4, 0, 0, 3, 10, 5} and the target sum is 7.

Output:

Sum found between indexes 1 and 4

This is because the numbers from index 1 to 4 are 4, 0, 0, 3, and their sum is 4 + 0 + 0 + 3 = 7.

In this article, we will look at two simple methods to solve this problem:

  1. Naive Approach: Try all possible groups of numbers to find the right one.
  2. Sliding Window Approach: Faster way that checks numbers in a smart, efficient way by using a moving window.
Sub-array with given sum in Java

Approach to solve Sub array with a given sum....

1. Naive Approach

Naive approach to finding a sub array with a given sum in Java checks every possible group of numbers in the array. It uses two loops, one to pick a starting point and another to try all ending points.

For each group, it calculates the total. If the total equals the target sum, it prints the starting and ending positions.

How It Works ?

  1. Start with an array and the target sum.
  2. Use a loop to pick a starting point in the array.
  3. From that starting point, use another loop to add the next numbers one by one.
  4. Keep adding numbers until the total:
  • Equals the target → print the start and end index.
  • Becomes greater than the target → stop checking this group.

Note: If no such group is found, print a message saying no sub array was found.

Algorithm:

  1. Take the array and target sum as input.

  2. Use a variable curr_sum to keep track of the current total.

  3. Loop from index i = 0 to the end:

    • Set curr_sum = arr[i].

    • Loop from j = i + 1 to the end:

      • Add arr[j] to curr_sum.

      • If curr_sum == target, print:
        "Subarray found between indexes i and j" and stop.

      • If curr_sum > target, stop the inner loop and move to next i.

  4. If no sub-array is found, print:
    "No sub-array found".

Java code for Naive Approach

Run

public class SubarrayWithGivenSumNaive {
    public static void findSubarray(int[] arr, int targetSum) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int currSum = arr[i];

            for (int j = i + 1; j <= n; j++) { if (currSum == targetSum) { System.out.println("Subarray found between indexes " + i + " and " + (j - 1)); return; } if (j == n || currSum > targetSum)
                    break;

                currSum += arr[j];
            }
        }

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

    public static void main(String[] args) {
        int[] arr = {1, 4, 0, 0, 3, 10, 5};
        int targetSum = 7;
        findSubarray(arr, targetSum);
    }
}

Output:

Subarray found between indexes 1 and 4

2. Sliding Window Approach (Efficient Method)

Sliding window approach is a faster method to solve this problem. It uses two pointers (start and i) to create a “window” that moves through the array. 

While moving, it keeps track of the sum of numbers inside the window. If the sum matches the target, it prints the indices.

How It Works ?

  1. Start with an array and a target sum.
  2. Initialize start to 0 and curr_sum to the first element.
  3. Loop through the array starting from index 1:
  • If curr_sum is more than the target, remove elements from the start of the window.

  • If curr_sum equals the target, print the start and end index.

  • If curr_sum is less than the target, add the current element to the sum.

Note: If no such sub array is found, print a message.

Algorithm:

  1. Take the array and target sum as input.

  2. Set start = 0 and curr_sum = arr[0].

  3. Loop from i = 1 to the end of the array:

    • While curr_sum > target and start < i - 1:

      • Subtract arr[start] from curr_sum.

      • Increase start by 1.

    • If curr_sum == target, print:
      "Subarray found between indexes start and i - 1" and stop.

    • If i < array length, add arr[i] to curr_sum.

  4. If no sub-array is found, print:
    "No sub-array found".

Java Code for Sliding Window Approach

Run

public class SubarrayWithGivenSumSlidingWindow {
    public static void findSubarray(int[] arr, int targetSum) {
        int n = arr.length;
        int currSum = arr[0], start = 0;

        for (int i = 1; i <= n; i++) { // Remove elements from the start while current sum is greater than the target while (currSum > targetSum && start < i - 1) {
                currSum -= arr[start];
                start++;
            }

            // Check if current sum matches the target
            if (currSum == targetSum) {
                System.out.println("Subarray found between indexes " + start + " and " + (i - 1));
                return;
            }

            // Add next element to current sum if not at the end
            if (i < n) {
                currSum += arr[i];
            }
        }

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

    public static void main(String[] args) {
        int[] arr = {1, 4, 0, 0, 3, 10, 5};
        int targetSum = 7;
        findSubarray(arr, targetSum);
    }
}

Output:

Subarray found between indexes 1 and 4

To wrap it up….

  • Finding a sub array with a given sum is a common and useful problem in programming.
  • It teaches us how to work with arrays, loops, and different ways to solve a problem efficiently.

We explored two methods:

  1. Naive Approach, which is simple but slower, and
  2. Sliding Window Approach, which is faster but works only when all numbers are non negative.

Understanding both methods helps you improve your problem solving skills and prepares you for coding interviews or competitive programming.

With a bit of practice, this problem becomes easy to understand and solve!

FAQ's related to Sub array with Given Sum

Answer:

Sub array is a part of an array that contains a sequence of elements next to each other.

For example, in the array {1, 2, 3, 4}, a sub array could be {2, 3} or {1, 2, 3}.

Answer:

It means we want to find a group of numbers in the array (placed one after another) that add up to a specific number.

For example, if the array is {1, 2, 3, 4} and the target sum is 5, the sub array {2, 3} works because 2 + 3 = 5.

Answer:

Yes, it’s possible to have multiple sub arrays that add up to the same target sum. But in many programs, we stop at the first one we find unless asked to find all of them.

Answer:

  1. The Naive Approach works with both positive and negative numbers.
  2. The Sliding Window Approach only works with non negative numbers (positive numbers and zero).

If the array has negative numbers, it might not give correct results.

Answer:

This problem helps you:

  1. Learn how to work with arrays.
  2. Practice loops and conditions.
  3. Understand how to optimize your code.
  4. Prepare for coding interviews and algorithm questions.

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription