## Target Sum Subarray

### March 19, 2019

Our solution finds the subarray in a single scan by keeping two pointers, `lo` and `hi`, and the `sum` between them, incrementing `hi` when `sum` is less than the `target`, incrementing `lo` when `sum` is greater than the `target`, and returning when `sum` is equal to the `target`; it fails when it reaches the end of the array without finding the `target`:

```(define (subarray vec target)
(let loop ((lo 0) (hi 1) (sum (vector-ref vec 0)))
(display lo) (display " ") (display hi)
(display " ") (display sum) (display " ")
(display (subvec vec lo hi)) (newline)
(cond ((= target sum) (list lo hi))
((< target sum) (loop (+ lo 1) hi (- sum (vector-ref vec lo))))
((= hi (vector-length vec)) #f)
(else (loop lo (+ hi 1) (+ sum (vector-ref vec hi)))))))```

Here `hi` is the next element past the end of the current subarray, which is more convenient. The only trick is arranging the `cond` clauses in the right order. Here are the example problems, with debugging output enabled so you can see what is happening:

```> (subarray '#(1 4) 3)
0 1 1 #(1)
0 2 5 #(1 4)
1 2 4 #(4)
2 2 0 #()
#f
> (subarray '#(1 4 0 0 3 10 5) 7)
0 1 1 #(1)
0 2 5 #(1 4)
0 3 5 #(1 4 0)
0 4 5 #(1 4 0 0)
0 5 8 #(1 4 0 0 3)
1 5 7 #(4 0 0 3)
(1 5)
> (subarray '#(1 4 20 3 10 5) 33)
0 1 1 #(1)
0 2 5 #(1 4)
0 3 25 #(1 4 20)
0 4 28 #(1 4 20 3)
0 5 38 #(1 4 20 3 10)
1 5 37 #(4 20 3 10)
2 5 33 #(20 3 10)
(2 5)
> (subarray '#(1 4 20 3 10) 33)
0 1 1 #(1)
0 2 5 #(1 4)
0 3 25 #(1 4 20)
0 4 28 #(1 4 20 3)
0 5 38 #(1 4 20 3 10)
1 5 37 #(4 20 3 10)
2 5 33 #(20 3 10)
(2 5)```

You can run the program at https://ideone.com/6djybl.

Pages: 1 2

### 6 Responses to “Target Sum Subarray”

1. Paul said

In Python.

```def sumsub(seq, target):
start, end, n, S = 0, 0, len(seq), 0
while end < n:
if S < target:
S += seq[end]
end += 1
elif S > target:
S -= seq[start]
start += 1
if S == target:
return start, end
raise ValueError("No solution")
```
2. ```(defun target-sum-subvector (target vector)
"Returns as multiple-values, the first bounding indices and the subvector whose elements sum to target."
(loop
:for start :below (length vector)
:do (loop
:for last :from start :below (length vector)
:for sum := (aref vector start) :then (+ sum (aref vector last))
;; :do (print (list start last sum))
:when (= sum target)
:do (return-from target-sum-subvector (values start (1+ last) (subseq vector start (1+ last))))
:while (< sum target))))

(assert (equalp (list
(multiple-value-list (target-sum-subvector 3 '#(1 4)))
(multiple-value-list (target-sum-subvector 7 '#(1 4 0 0 3 10 5)))
(multiple-value-list (target-sum-subvector 33 '#(1 4 20 3 10 5)))
(multiple-value-list (target-sum-subvector 33 '#(1 4 20 3 10))))
'((nil) (1 5 #(4 0 0 3)) (2 5 #(20 3 10)) (2 5 #(20 3 10)))))
```
3. James Curtis-Smith said

This one is beautifully built for perl – a little bit of golf here..

```use strict;
## Shift first parameter as total (we actually use -ve total to avoid 1 -ve)
my(\$s,\$e,\$d)=(0,0,shift);
## If diff is +ve need to get another number - if -ve we need to drop a number from total
## End if we have a zero total OR we have gone past the end of the array!
\$d+=\$d<0?-\$ARGV[\$e++]:\$ARGV[\$s++]while\$e<=@ARGV&&\$d;
```
4. James Curtis-Smith said

```\$d=shift;
\$d+=\$d<0?-\$ARGV[\$e++]:\$ARGV[\$s++]while\$e<=@ARGV&&\$d;
```
5. Daniel said

Here’s a solution in C.

```#include <stdio.h>
#include <stdlib.h>

void print_array(int* array, int n) {
printf("[");
for (int i = 0; i < n; ++i) {
if (i > 0) printf(",");
printf("%d", array[i]);
}
printf("]");
}

int find_target(
int* array, int n, int target, int* start, int* len) {
if (n == 0) return 0;
int sum = array;
int left = 0;
int right = 0;
while (left < n && right < n) {
if (sum == target) {
*start = left;
*len = right - left + 1;
return 1;
}
if (sum > target) {
sum -= array[left++];
} else {
sum += array[++right];
}
}
return 0;
}

int main(int argc, char* argv[]) {
if (argc < 2) return EXIT_FAILURE;
int target = atoi(argv);
int n = argc - 2;
int* array = malloc(n * sizeof(array));
for (int i = 0; i < n; ++i) {
array[i] = atoi(argv[i + 2]);
}
int start;
int len;
int success = find_target(array, n, target, &start, &len);
if (success) {
print_array(array + start, len);
printf("\n");
}
free(array);
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out 33 1 4 20 3 10 5
[20,3,10]
\$ ./a.out 7 1 4 0 0 3 10 5
[4,0,0,3]
\$ ./a.out 3 1 4
```
6. Globules said

Here’s a Haskell version that works for negative numbers and non-integers as well. It uses a map to keep track of the cumulative sum of the elements so that it can make a single pass through the list. (It trades time for space.) Note that Haskell has a particular way of printing rational numbers: 2/5 is 2 % 5, -1/3 is (-1) % 3, etc.

```import Prelude hiding (lookup)
import Data.Foldable (asum)
import Data.List (scanl')
import Data.Map (empty, insert, lookup)

-- Find the first sublist whose elements sum to the target value.  The result is
-- Nothing if no sublist can be found, otherwise it's Just (i, j), where i is
-- the zero-based index of the first element and j is the length.
--
-- Looking for a sublist that sums to 0 will always return the empty list.
subsum :: (Num a, Ord a) => a -> [a] -> Maybe (Int, Int)
subsum targ = fmap offlen . asum . look . drop 1 . maps . sums
where sums   = zip [0..] . scanl' (+) 0
maps   = scanl' (\(_, m) (v, k) -> (k, insert k v m)) (0, empty)
look   = map (\(x, m) -> (,) <\$> lookup (x - targ) m <*> lookup x m)
offlen = \(x, y) -> (x, y - x)

main :: IO ()
main = do
mapM_ test [ (33, [1, 4, 20, 3, 10, 5] :: [Int])
, ( 7, [1, 4, 0, 0, 3, 10, 5]),
( 3, [1, 4])
]
putStrLn ""
mapM_ test [ (0,  :: [Int])
, (1, [0..])
]
putStrLn ""
mapM_ test [ (-3/2, [2/3, -5/6, 1, -5/3, 7/2] :: [Rational]) ]

test :: (Num a, Ord a, Show a) => (a, [a]) -> IO ()
test (targ, xs) = do
putStr \$ show targ
case subsum targ xs of
```\$ ./subsum