Given an array of integers and an integer target, find a subarray that sums to target and return the start and end indices of the subarray. It's guaranteed to have a unique solution.
Input:
11 -20 -3305427
Output: 1 4
Explanation: -20 - 3 + 30 = 7. The indices for subarray [-20,-3,30] is 1 and 4 (right exclusive).
Try it yourself
Explanation
Intuition
The brute force way is to find the sum of each subarray and compare it with the target. Let N be the number of elements in the array. There are N subarrays with size 1, N-1 subarrays with size 2 .. and 1 subarray with size N. Time complexity is O(N^2).
A key observation is the the sum of a subarray [i, j] is equal to the sum of [0, j] minus the sum of [0, i - 1].
The sum of elements from index 0 to i is called the prefix sum. If we have the subarray sum for each index, we can find the sum of any subarray in constant time.
With the knowledge of prefix sum under our belt, the problem boils down to Two Sum. We keep a dictionary of prefix_sum: index while going through the array calculating prefix_sum. If at any point, prefix_sum - target is in the dictionary we have found our subarray.
1from typing importList23defsubarray_sum(arr: List[int], target: int) -> List[int]:4# prefix_sum 0 happens when we have an empty array5 prefix_sums = {0: 0}
6 cur_sum = 07for i inrange(len(arr)):
8 cur_sum += arr[i]
9 complement = cur_sum - target
10if complement in prefix_sums:
11return [prefix_sums[complement], i + 1]
12 prefix_sums[cur_sum] = i + 11314if __name__ == '__main__':
15 arr = [int(x) for x ininput().split()]
16 target = int(input())
17 res = subarray_sum(arr, target)
18print(' '.join(map(str, res)))
19
1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
67classSolution{
8publicstatic List<Integer> subarraySum(List<Integer> arr, int target){
9 HashMap<Integer, Integer> prefixSums = new HashMap<>();
10// prefix_sum 0 happens when we have an empty array11 prefixSums.put(0, 0);
12int curSum = 0;
13for (int i = 0; i < arr.size(); i++) {
14 curSum += arr.get(i);
15int complement = curSum - target;
16if (prefixSums.containsKey(complement)) {
17return List.of(prefixSums.get(complement), i + 1);
18 }
19 prefixSums.put(curSum, i + 1);
20 }
21returnnull;
22 }
2324publicstatic List<String> splitWords(String s){
25return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
26 }
2728publicstaticvoidmain(String[] args){
29 Scanner scanner = new Scanner(System.in);
30 List<Integer> arr = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
31int target = Integer.parseInt(scanner.nextLine());
32 scanner.close();
33 List<Integer> res = subarraySum(arr, target);
34 System.out.println(res.stream().map(String::valueOf).collect(Collectors.joining(" ")));
35 }
36}
37
1functionsubarraySum(arr, target) {
2// prefix_sum 0 happens when we have an empty array3const prefixSums = newMap([[0, 0]]);
4let curSum = 0;
5for (let i = 0; i < arr.length; i++) {
6 curSum += arr[i];
7const complement = curSum - target;
8if (prefixSums.has(complement)) {
9return [prefixSums.get(complement), i + 1];
10 }
11 prefixSums.set(curSum, i + 1);
12 }
13}
1415functionsplitWords(s) {
16return s == "" ? [] : s.split(' ');
17}
1819function* main() {
20const arr = splitWords(yield).map((v) =>parseInt(v));
21const target = parseInt(yield);
22const res = subarraySum(arr, target);
23console.log(res.join(' '));
24}
2526classEOFErrorextendsError{}
27{
28const gen = main();
29const next = (line) => gen.next(line).done && process.exit();
30let buf = '';
31 next();
32 process.stdin.setEncoding('utf8');
33 process.stdin.on('data', (data) => {
34const lines = (buf + data).split('\n');
35 buf = lines.pop();
36 lines.forEach(next);
37 });
38 process.stdin.on('end', () => {
39 buf && next(buf);
40 gen.throw(new EOFError());
41 });
42}
43
Note that in the implementation, typically we use prefix_sum[i] to denote the sum of elements in 0...i - 1 (rightmost element i is not included in the sum). One good thing about this is prefix_sum[0] then means sum of array up to but not including the first element, i.e. empty array. The definition of empty array sum is useful when there exists a subarray starting from 0 that sums up to the target. Without the definition of empty array sum we would miss it because its complement 0 does not exist in the dictionary.
Follow up
Find the total number of subarrays that sums up to target.
Explanation
Since the new problem does not ask for index but total number instead, we can change our hashmap to "sum k: number of prefix sums that sums up to k".
1from typing import Counter, List23defsubarray_sum_total(arr: List[int], target: int) -> int:4 prefix_sums = Counter()
5 prefix_sums[0] = 1# since empty array's sum is 06 cur_sum = 07 count = 08for i inrange(len(arr)):
9 cur_sum += arr[i]
10 complement = cur_sum - target
11if complement in prefix_sums:
12 count += prefix_sums[complement]
13 prefix_sums[cur_sum] += 114return count
1516if __name__ == '__main__':
17 arr = [int(x) for x ininput().split()]
18 target = int(input())
19 res = subarray_sum_total(arr, target)
20print(res)
21
