Indexes of Subarray Sum
Problem Description
Given an array of non-negative integers, find the indices of the first subarray whose sum equals a specified target. If no such subarray exists, return [-1]
.
Example:
- Input:
arr[] = [1, 2, 3, 7, 5]
,target = 12
- Output:
[2, 4]
- Explanation: The sum of elements from the 2nd to the 4th position is
2 + 3 + 7 = 12
.
Solution Code
class Solution {
static ArrayList<Integer> subarraySum(int[] arr, int target) {
ArrayList<Integer> result = new ArrayList<>();
int n = arr.length;
int left = 0;
int currentSum = 0;
for (int right = 0; right < n; right++) {
currentSum += arr[right];
while (currentSum > target && left <= right) {
currentSum -= arr[left];
left++;
}
if (currentSum == target) {
result.add(left + 1); // 1-based index
result.add(right + 1); // 1-based index
return result;
}
}
result.add(-1);
return result;
}
}
Hint
- Use a sliding window approach to maintain a window of elements whose sum is less than or equal to the target. Adjust the window by moving the left pointer if the sum exceeds the target.
Approach Name
Sliding Window Technique
Intuition
The sliding window technique is efficient for problems involving subarrays or substrings. By maintaining a window that expands and contracts based on the sum of elements within it, we can efficiently find the subarray that meets the target sum.
Algorithm
- Initialize two pointers,
left
andright
, to the start of the array. - Use a variable
currentSum
to keep track of the sum of elements within the current window. - Iterate through the array with the
right
pointer, adding each element tocurrentSum
. - If
currentSum
exceeds the target, move theleft
pointer to the right and subtract the element at theleft
pointer fromcurrentSum
. - If
currentSum
equals the target, return the 1-based indices of theleft
andright
pointers. - If no such subarray is found by the end of the array, return
[-1]
.
Test Input
1 2 3 7 5, 12
Complexity Analysis
- Time Complexity: O(n), where
n
is the number of elements in the array. Each element is processed at most twice (once when expanding the window and once when contracting it). - Space Complexity: O(1), as we are using a constant amount of extra space.
This solution efficiently finds the first subarray that sums to the target using a sliding window approach, ensuring optimal performance even for large arrays.