Find Subarray With Given Sum in Java
Problem
A subarray with a given sum is a contiguous run of elements — not just any selection — whose values add up to exactly a target number.
Given an array of non-negative integers and a target sum, find a contiguous subarray that adds up to the target.
Java Program
import java.util.Arrays;
public class SubarrayWithGivenSum {
public static void main(String[] args) {
int[] arr = {2, 6, 1, 3, 4, 9, 5};
int target = 10;
int foundStart = -1, foundEnd = -1;
outer:
for (int i = 0; i < arr.length; i++) {
int sum = 0; // reset for each new starting index
for (int j = i; j < arr.length; j++) {
sum += arr[j]; // extend the candidate window by one element
if (sum == target) {
foundStart = i;
foundEnd = j;
break outer; // exits both loops at once
}
}
}
int[] result = Arrays.copyOfRange(arr, foundStart, foundEnd + 1);
System.out.println(Arrays.toString(result));
}
}Output
Core Logic
Extending a candidate subarray one element at a time from every possible starting point, and stopping as soon as its running sum hits the target, checks every contiguous window directly.
- 1The outer loop picks a starting index
ifor a candidate subarray. - 2The inner loop extends the subarray by adding
arr[j]to a runningsum. - 3
sum == targetchecks whether the subarray built so far matches exactly — a labeledbreak outerexits both loops immediately on a match. - 4
Arrays.copyOfRange(arr, foundStart, foundEnd + 1)extracts the matching subarray using the indices recorded at the moment of the match.
[2, 6, 1, 3, 4, 9, 5] with target = 10, starting at index 1, the running sum reaches 6 + 1 + 3 = 10 exactly, producing [6, 1, 3].Key Point: This works for any array of integers, including negative ones — trying every starting point separately doesn't rely on the running sum only ever increasing.
Why: Every candidate window's sum is computed directly by extending the inner loop, so the nested loops do up to O(n²) work in the worst case.
Key Concepts
Approach 2: Sliding Window
import java.util.Arrays;
public class SubarrayWithGivenSumWindow {
public static void main(String[] args) {
int[] arr = {2, 6, 1, 3, 4, 9, 5};
int target = 10;
int start = 0, sum = 0;
int foundStart = -1, foundEnd = -1;
for (int end = 0; end < arr.length; end++) {
sum += arr[end]; // grow the window from the right
while (sum > target && start < end) { // shrink from the left while over target
sum -= arr[start];
start++;
}
if (sum == target) {
foundStart = start;
foundEnd = end;
break;
}
}
int[] result = Arrays.copyOfRange(arr, foundStart, foundEnd + 1);
System.out.println(Arrays.toString(result));
}
}
Output
Core Logic
For an array of non-negative numbers, a window that only ever grows forward and shrinks from the back — never restarting from scratch — can find the same answer without ever re-scanning already-checked elements.
- 1
startandsumtrack the window's left edge and running total, both beginning at0. - 2The loop advances
endforward, addingarr[end]tosumeach time — growing the window. - 3
while (sum > target && start < end)shrinks the window from the left, subtractingarr[start]and advancingstart, whenever the running sum overshoots the target. - 4
sum == targetafter the shrink step means the current window is the answer.
[2, 6, 1, 3, 4, 9, 5] with target = 10, the window grows to [2, 6, 1, 3] (sum 12), shrinks by dropping the leading 2 down to [6, 1, 3] (sum 10), and stops there.Key Point: The shrink step's correctness depends on every number being non-negative — with negative numbers allowed, removing an element from the front wouldn't reliably shrink the sum, since a later negative could have been dragging it down.
Why: Each element is added to the window once and removed at most once as the window shrinks, so the total work stays linear despite the nested-looking while loop.