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.

Advertisements

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
    print$d?"NOT FOUND\n":"@ARGV[$s..--$e]\n"; 
    
  4. James Curtis-Smith said

    Without the comments and stricture….

    $d=shift;
    $d+=$d<0?-$ARGV[$e++]:$ARGV[$s++]while$e<=@ARGV&&$d;
    print$d?"NOT FOUND\n":"@ARGV[$s..--$e]\n";
    
  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
        Nothing     -> putStrLn " not found"
        Just (i, j) -> putStrLn $ " = sum " ++ show (take j $ drop i xs)
    
    $ ./subsum
    33 = sum [20,3,10]
    7 = sum [4,0,0,3]
    3 not found
    
    0 = sum []
    1 = sum [1]
    
    (-3) % 2 = sum [(-5) % 6,1 % 1,(-5) % 3]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: