NUMRANGE

Given an array of non negative integers A, and a range (B, C),
find the number of continuous subsequences in the array which have sum S in the range [B, C] or B <= S <= C

Continuous subsequence is defined as all the numbers A[i], A[i + 1], .... A[j]
where 0 <= i <= j < size(A)

A : [10, 5, 1, 0, 2]
(B, C) : (6, 8)

ans = 3
as [5, 1], [5, 1, 0], [5, 1, 0, 2] are the only 3 continuous subsequence with their sum in the range [6, 8]

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public int numRange(ArrayList<Integer> A, int B, int C) {
        return subArrayLessThanOrEqualTo(A, C) - subArrayLessThanOrEqualTo(A, B - 1);
    }
    
    private int subArrayLessThanOrEqualTo(ArrayList<Integer> A, int B) {
        int left = 0;
        int right = 0;
        int sum = A.get(0);
        int num = 0;
        while (left < A.size() && right < A.size()) {
            if (sum <= B) {
                if (right >= left) {
                    num += right - left + 1;
                }
                right ++;
                if (right < A.size()) {
                    sum += A.get(right);
                }
            } else {
                sum -= A.get(left);
                left ++;
            }
        }
        return num;
    }
}