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)

Have you met this question in a real interview?

Yes

Example

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

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

line 20 parameter value
A[i] + end + 1 not end + 1 find difference


class Solution {
public:
    /**
     * @param A an integer array
     * @param start an integer
     * @param end an integer
     * @return the number of possible answer
     */
    int subarraySumII(vector<int>& A, int start, int end) {
        // Write your code here
        if (A.empty()) {
            return 0;
        }
        for (int i = 1; i < A.size(); ++i) {
            A[i] += A[i - 1];
        }
        A.insert(A.begin(), 0);
        int count = 0;
        for (int i = 0; i < A.size(); ++i) {
            count += countLessThan(A, A[i] + end + 1) - countLessThan(A, A[i] + start);
        }

        return count;
    }

private:
    int countLessThan(const vector<int>& A, int value) {
        int start = 0, end = A.size() - 1;
        while (start + 1 < end) {
            int mid = start + (end - start >> 1);
            if (A[mid] >= value) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (A[end] < value) {
            return end + 1;
        } else if (A[start] < value) {
            return start + 1;
        } else {
            return 0;
        }
    }
};