title: Google Interview: Find all contiguous subsequence in a given array of integers, whose sum falls in the given range. Can we do better than O(n^2)?
body: <blockquote>
    <p>Given an array of Integers, and a range (low, high), find all
    contiguous subsequence in the array which have sum in the range.</p>
    
    <p>Is there a solution better than O(n^2)?</p>
  </blockquote>
  
  <p>I tried a lot but couldn't find a solution that does better than O(n^2). Please help me find a better solution or confirm that this is the best we can do. </p>
  
  <p>This is what I have right now, I'm assuming the range to be defined as <code>[lo, hi]</code>.</p>
  
  <pre class="lang-java prettyprint-override"><code>public static int numOfCombinations(final int[] data, final int lo, final int hi, int beg, int end) {
      int count = 0, sum = data[beg];
  
      while (beg &lt; data.length &amp;&amp; end &lt; data.length) {
         if (sum &gt; hi) {
            break;
         } else {
            if (lo &lt;= sum &amp;&amp; sum &lt;= hi) {
              System.out.println("Range found: [" + beg + ", " + end + "]");
              ++count;
            }
            ++end;
            if (end &lt; data.length) {
               sum += data[end];
            }
         }
      }
      return count;
  }
  
  public static int numOfCombinations(final int[] data, final int lo, final int hi) {
      int count = 0;
  
      for (int i = 0; i &lt; data.length; ++i) {
          count += numOfCombinations(data, lo, hi, i, i);
      }
  
      return count;
  }
  </code></pre>