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.
Programming Praxis 
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")(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)))))This one is beautifully built for perl – a little bit of golf here..
Without the comments and stricture….
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:
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 Nothing -> putStrLn " not found" Just (i, j) -> putStrLn $ " = sum " ++ show (take j $ drop i xs)