count of sequences of array elements with appropriate sum

Provided that the integers are all non-negative, you could use this algorithm (pseudo-code):

countInRange(a, l, m): sumL = 0 count = 0 idxM = 0 i = 1 idxLast = len(a) for idxL = 1 to idxLast: sumL = sumL + a[idxL] while i <= idxLast and sumL >= l: if idxM <= idxL: idxM = idxL sumM = sumL while idxM <= idxLast and sumM <= m: idxM = idxM + 1 if idxM > idxLast: break sumM = sumM + a[idxM] count = count + idxM - idxL sumL = sumL - a[i] sumM = sumM - a[i] i = i + 1 return count 

This algorithm runs with O(n) time complexity:

In total, the inner-most loop will never iterate more than n times. This is because the value of idxM at entering the loop:

• is never lower than 1
• is never higher than n
• is always at least one greater than the previous time the loop was entered.

In total the middle loop will never execute more than n times either, as it increments i to n, and the same is clearly true for the outer loop.

I guess the following algorithm should do the job. I tried to implement it in JS. It's basically a single reduce operation with an initial value like {idx:0, len:0, sum:0} and there is a 3 level nested ternary inside.

For testing purposes I have generated an array of 30 items with random values between 1 - 10. Currently it gives the result as the series, for you to help me check if it's working well. Then as per your request the series counts, all we need is to replace the last

return r[0].sum < low ? r.slice(1) : r; 

line with

return r[0].sum < low ? r.length-1 : r.length; 

function getLimitedSeries(a,low,high){ var r = a.reduce((p,c,i) => (p[0].sum + c < low ? ( p[0].sum += c, p[0].len++ ) : p[0].sum + c <= high ? ( p[0].sum += c, p[0].len++, p[0].idx = i-p[0].len+1 ) : ( p[0].sum >= low && p.push(p[0]), p[0] = c > high ? {idx:i, len:0, sum:0} : {idx:i, len:1, sum:c} ),p) , [{idx:0, len:0, sum:0}]); // initial value of reduce return r[0].sum < low ? r.slice(1) : r; } var arr = new Array(30).fill().map(e => ~~(Math.random()*10)+1); console.log(JSON.stringify(arr)); console.log(getLimitedSeries(arr,15,21));