Finding if sequential numbers for total exists

Question:
Given a sequence of positive integers A and an integer T, return whether there is a continuous sequence of A that sums up to exactly T

Example:

A = [23, 5, 4, 7, 2, 11], T = 20: True because 7 + 2 + 11 = 20

A = [1, 3, 5, 23, 2], T = 8: True because 3 + 5 = 8

A = [1, 3, 5, 23, 2], T = 7: False because no sequence in this array adds up to 7

Write code to find if sequential numbers for total exists.

Note: I'm looking for an O(N) solution. There is an obvious O(N^2) solution but is not the final solution I'm looking for.

My answer code (in ruby) is the following. Please let me know if there is a more efficient way.

class Sequence
  def initialize(integers)
    @integers = integers
  end

  def continuous_sequence_for_total_exists?(total)
    sliced_array = slice_array(total)
    sliced_array.each do |array|
      array.each do
        if array.reduce(:+) == total
          return true
        else
          array.shift
        end
      end
    end

    return false
  end

  private

  # Slice array with any integer larger than max
  #
  # e.g.:
  # [1, 3, 5, 23, 2] => [1, 3, 5], [2]
  def slice_array(max)
    chunks = @integers.chunk{ |i| i < max || nil }
    chunks.map{ |answer, value| value }
  end
end

Your code incorrectly returns false if I give it [23, 5, 4, 7, 2, 11, 1] and a target value of 20. The answer should still be 7 + 2 + 11, but it doesn't find it.

That's because the reduce operation always runs to the end of the array, so it is unable to pick out a matching sub-sequence in the middle of a larger sequence. It can only find it, if it's at the end. I.e. it does this:

5 + 4 + 7 + 2 + 11 + 1 => 30
4 + 7 + 2 + 11 + 1     => 25
7 + 2 + 11 + 1         => 21
2 + 11 + 1             => 13 # could just give up here, really
11 + 1                 => 12
1                      => 1

=> false

However 2 + 7 + 11 would've been a valid answer.

Your example input just happens to be crafted so that you get correct results; the matching sub-sequences are always anchored to the end of an array. They're never in the middle of it.

Furthermore, by chunking using i < max you remove values that are equal to the target sum. I.e. trying [1, 3, 7, 5, 23, 2] with a target of 7 will fail, even though there is a sequence - a sequence of 1 value - that matches.

This is however easily fixed by changing the block to use i <= max.

Overall, I'd propose something like this:

def sub_sequence_equal_to?(total, values)
  sequences = values.chunk { |n| n  total
      return true if sum == total
      sum
    end
  end

  false
end

It'll gradually build a sum, but also subtract the earliest values if said sum has grown too large.

So given [23, 5, 4, 7, 2, 11, 1] and a target value of 20 it'll do something like:

5                  => 5
5 + 4              => 9
5 + 4 + 7          => 16
5 + 4 + 7 + 2      => 18
5 + 4 + 7 + 2 + 11 => 29
    4 + 7 + 2 + 11 => 24
        7 + 2 + 11 => 20

=> true

It's not quite \$O(n)\$, and perhaps there's a smarter way (it'd be nice to get rid of that separate chunk step for instance). Still, it's more efficient (and works better) than the original.

StackExchange Code Review Q#115152, answer score: 5