Problem

Given an integer array, find a subarray where the sum of numbers is in a given interval. 
Your code should return the number of possible answers. (The element in the array should be positive)

Example
Given [1,2,3,4] and interval = [1,3], return 4. The possible answers are:

[0, 0]
[0, 1]
[1, 1]
[2, 2]

思路

举一个🌰
    A = [1, 2, 3, 4]             start = 1, end = 3                                
    ps = [0, 1, 3, 6, 10]

    n = A.length    

assume we have index i and j separately representing the end and the start of the subarray, i > j.
we got a formula
        start <= ps[i] - ps[j] <= end
then
        start + ps[j] <= ps[i] <= end + ps[j]
where
       1 <= i <= n, 0 < j < i
so
        2 for loop, time complexity is O(n)

    public int subarraySumII(int[] A, int start, int end) {
        if (A == null) return 0;
        int n = A.length;
        if (n == 0) return 0;

        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + A[i];
        }

        int count = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if ((prefixSum[i] <= prefixSum[j] + end) && (prefixSum[i] >= start + prefixSum[j])) {
                    count++;  
                } 
            }
        }

        return count;
    }

Optimization

An important condition haven't been used:
        The element in the array should be positive.
                meaning that the prefix sum array is in ascending order.

so 
        1. sorted array
        2. count
        3. a range

use binary search

previous example
                start + ps[j] <= ps[i] <= end + ps[j]

lower bound is 
                start + ps[j]
upper bound is
                end + ps[j]

go find index of two bound