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
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:
- Naive Approach: Try all possible groups of numbers to find the right one.
- Sliding Window Approach: Faster way that checks numbers in a smart, efficient way by using a moving window.
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 ?
- Start with an array and the target sum.
- Use a loop to pick a starting point in the array.
- From that starting point, use another loop to add the next numbers one by one.
- 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:
Take the array and target sum as input.
Use a variable
curr_sumto keep track of the current total.Loop from index
i = 0to the end:Set
curr_sum = arr[i].Loop from
j = i + 1to the end:Add
arr[j]tocurr_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 nexti.
If no sub-array is found, print:
"No sub-array found".
Time Complexity: O(n2)
Space Complexity: O(1)
Java code for Naive Approach
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
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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 ?
- Start with an array and a target sum.
- Initialize start to 0 and curr_sum to the first element.
- Loop through the array starting from index 1:
If
curr_sumis more than the target, remove elements from the start of the window.If
curr_sumequals the target, print the start and end index.If
curr_sumis less than the target, add the current element to the sum.
Note: If no such sub array is found, print a message.
Algorithm:
Take the array and target sum as input.
Set
start = 0andcurr_sum = arr[0].Loop from
i = 1to the end of the array:While
curr_sum > targetandstart < i - 1:Subtract
arr[start]fromcurr_sum.Increase
startby 1.
If
curr_sum == target, print:"Subarray found between indexes start and i - 1"and stop.If
i < array length, addarr[i]tocurr_sum.
If no sub-array is found, print:
"No sub-array found".
Time Complexity: O(n)
Space Complexity: O(1)
Java Code for Sliding Window Approach
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:
- Naive Approach, which is simple but slower, and
- 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:
- The Naive Approach works with both positive and negative numbers.
- 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:
- Learn how to work with arrays.
- Practice loops and conditions.
- Understand how to optimize your code.
- 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
Login/Signup to comment