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] =&gt; [1, 3, 5], [2]
  def slice_array(max)
    chunks = @integers.chunk{ |i| i &lt; 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 =&gt; 30
4 + 7 + 2 + 11 + 1     =&gt; 25
7 + 2 + 11 + 1         =&gt; 21
2 + 11 + 1             =&gt; 13 # could just give up here, really
11 + 1                 =&gt; 12
1                      =&gt; 1

=&gt; 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 &lt; 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 &lt;= max.

Overall, I'd propose something like this:

def sub_sequence_equal_to?(total, values)
  sequences = values.chunk { |n| n &lt;= total || nil }.map(&amp;:last)

  sequences.each do |sequence|
    sequence.reduce(0) do |sum, n|
      sum += n
      sum -= sequence.shift while sum &gt; 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                  =&gt; 5
5 + 4              =&gt; 9
5 + 4 + 7          =&gt; 16
5 + 4 + 7 + 2      =&gt; 18
5 + 4 + 7 + 2 + 11 =&gt; 29
    4 + 7 + 2 + 11 =&gt; 24
        7 + 2 + 11 =&gt; 20

=&gt; 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.