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.

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: