880847. Search for Subarray
Medium
Search for Subarray
Slug: search-for-subarray
Difficulty: Medium
Id: 880847
Topic Tags: None
Company Tags: None
Summary
Given an array of integers and a target sum, find all subarrays that have the given sum. The problem is similar to the well-known "Subarray Sum" problem, but with the additional requirement to return all subarrays that satisfy the condition.
Detailed Explanation
To solve this problem, we can use a combination of hash tables and dynamic programming. Here's a step-by-step breakdown of the solution:
- Initialize an empty hash table (e.g., HashMap in Java or Python dictionary) to store the cumulative sum and its corresponding index.
- Iterate through the array, calculating the cumulative sum at each position. For each cumulative sum, check if it equals the target sum.
- If the cumulative sum equals the target sum, add the current index and all previous indices (calculated using the hash table) to a list of results.
- Continue iterating through the array until the end is reached.
Here's an ASCII art diagram illustrating the algorithm:
+---------------+
| Input Array |
+---------------+
|
v
+-----------------------+
| Cumulative Sum |
| Hash Table |
+-----------------------+
|
v
+---------------------------------+
| Iterate through array, checking |
| cumulative sum and target sum |
+---------------------------------+
The time complexity of this solution is O(n), where n is the length of the input array. The space complexity is also O(n) due to the hash table.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class SearchForSubarray {
public static List<Integer[]> findSubarrays(int[] arr, int targetSum) {
Map<Integer, Integer> cumulativeSumMap = new HashMap<>();
List<Integer[]> results = new ArrayList<>();
int cumulativeSum = 0;
for (int i = 0; i < arr.length; i++) {
cumulativeSum += arr[i];
if (cumulativeSum == targetSum) {
results.add(new Integer[]{i, cumulativeSum});
}
if (cumulativeSumMap.containsKey(cumulativeSum - targetSum)) {
int start = cumulativeSumMap.get(cumulativeSum - targetSum);
for (int j = start; j <= i; j++) {
results.add(new Integer[]{j, cumulativeSum});
}
}
cumulativeSumMap.put(cumulativeSum, i);
}
return results;
}
}