Programming Praxis

6 Responses to “Target Sum Subarray”

1. Paul said

   March 19, 2019 at 9:44 AM

   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. Pascal Bourguignon said

   March 19, 2019 at 10:38 AM

   (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

   March 19, 2019 at 12:12 PM

   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

   March 19, 2019 at 12:18 PM

   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

   March 28, 2019 at 5:33 PM

   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

   April 1, 2019 at 3:21 AM

   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]