0.question.md

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 [23, 5, 4, 7, 2, 11], 20. Return True because 7 + 2 + 11 = 20 [1, 3, 5, 23, 2], 8. Return True because 3 + 5 = 8 [1, 3, 5, 23, 2], 7 Return False because no sequence in this array adds up to 7

Note: We are looking for an O(N) solution. There is an obvious O(N^2) solution which is a good starting point but is not the final solution we are looking for.

1.my_solution.rb

require 'rspec'

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

  def sub_sequence_equal_to?(target)
    puts "target: #{target}"

    summary = 0
    window = []
    source = @integers

    while !(source.empty? && (window.empty? || summary < target))
      puts [window, source, summary].inspect

      return true if summary == target || source.first == target

      if summary > target
        summary -= window.first
        window = window[1..-1]
      elsif !source.empty? && source.first > target
        summary = 0
        window = []
        source = source[1..-1]
      else
        summary += source.first
        window = window + [source.first]
        source = source[1..-1]
      end
    end

    false
  end
end

describe Sequence do
  describe "#sub_sequence_equal_to?" do

    subject { sequence.sub_sequence_equal_to?(target) }

    # NOTE Examples ending with '^' are those provided in your question
    context "when total of continuous sub sequence is equal to target" do
      context "and first number is larger than target^" do
        let(:sequence) { Sequence.new([23, 5, 4, 7, 2, 11, 1]) }
        let(:target) { 20 }

        it { is_expected.to be_truthy }
      end
      context "and the subset sits in the middle^" do
        let(:sequence) { Sequence.new([1, 3, 5, 23, 2]) }
        let(:target) { 8 }

        it { is_expected.to be_truthy }
      end
      context "and Sequence begings with the sub set" do
        let(:sequence) { Sequence.new([3, 5, 23, 2]) }
        let(:target) { 8 }

        it { is_expected.to be_truthy }
      end
      context "and Sequence ends with the sub set" do
        let(:sequence) { Sequence.new([3, 2, 1, 8, 1, 2, 1]) }
        let(:target) { 4 }

        it { is_expected.to be_truthy }
      end
      context "and Sequence begings with number equal to target" do
        let(:sequence) { Sequence.new([8, 3, 5, 23, 2]) }
        let(:target) { 8 }

        it { is_expected.to be_truthy }
      end
      context "and Sequence ends with number equal to target" do
        let(:sequence) { Sequence.new([1, 5, 23, 2, 8]) }
        let(:target) { 8 }

        it { is_expected.to be_truthy }
      end
    end

    context "when total of continuous sub sequence is not equal to target^" do
      let(:sequence) { Sequence.new([1, 3, 5, 23, 2]) }
      let(:target) { 7 }

      it { is_expected.to be_falsey }
    end
  end
end

I introduced sliding window algorithm to my solution to make the calculation efficient.

There are two optimizations worth mentioning in this solution.

The first is that, any value that is exactly equal to the target triggers an immediate return. This skips some wasted iterations, for example:

target: 8
# [window, source, summary]
[[], [1, 5, 23, 2, 8], 0]
[[1], [5, 23, 2, 8], 1]
[[1, 5], [23, 2, 8], 6]
[[], [2, 8], 0]
[[2], [8], 2]  # => Returns true with the optimization
[[2, 8], [], 10]
[[8], [], 8] # => Returns true without the optimization

The second is that any value which is larger than the target and surrounding numbers are skipped because those steps always return false. For example:

target: 4
# [window, source, summary]
[[], [3, 2, 1, 8, 1, 2, 1], 0]
[[3], [2, 1, 8, 1, 2, 1], 3]
[[3, 2], [1, 8, 1, 2, 1], 5]
[[2], [1, 8, 1, 2, 1], 2]
[[2, 1], [8, 1, 2, 1], 3]

# Skipped:  [[2, 1, 8], [1, 2, 1], 3]
# Skipped:  [[1, 8], [1, 2, 1], 3]
# Skipped:  [[8], [1, 2, 1], 3]

[[], [1, 2, 1], 0]
[[1], [2, 1], 1]
[[1, 2], [1], 3]
[[1, 2, 1], [], 4]