Target Sum Subarray

March 19, 2019

Given an array of non-negative integers, write a program that finds the contiguous portion of the array that sums to a given target, or report that there is no such subarray. For instance, in the array 1, 4, 20, 3, 10, 5, target 33 exists in the subarray 20, 3, 10, in the array 1, 4, 0, 0, 3, 10, 5, target 7 exists in the subarray 4, 0, 0, 3, and in the array 1, 4, target 3 does not exist in any subarray.

Your task is to write a program that finds a target sum in an array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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;
## If diff is 0 display list o/w NOT FOUND
```
4. James Curtis-Smith said

Without the comments and stricture….

```\$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[0];
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[1]);
int n = argc - 2;
int* array = malloc(n * sizeof(array[0]));
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, [1] :: [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