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]

1. 求出sum和，并且枚举i, j分别代表区间的起点和终点，遇到和在target范围内的就结果加一
2. 求出sum和，因为数组内元素全部为正数，那么也就是说sum数组是升序排列的，这样我们可以通过这一步二分查找起点和终点， start <= sum[i] - x <= end, 可以求解x的区间， 便是我们需要二分查找的边界
   1. 在二分查找时，如果我们查找最后一个小于等于值的下标，因为有等于的情况，所以在等于时返回的下标和在小于时返回的下标会差一个数，这时我们可以通过查找左区间减一来保证这两种情况会得到相同的下标
   2. 如果当前sum[i]本身在区间中， 需要判断并加上这种情况
   3. 如果查找的边界小于等于0 或 大于等于sum中最大值，可以直接return 0

public class Solution {
    /*
     * @param A: An integer array
     * @param start: An integer
     * @param end: An integer
     * @return: the number of possible answer
     */
    public int subarraySumII(int[] A, int start, int end) {
        // write your code here
        if (A == null || A.length == 0) {
            return 0;
        }

        int n = A.length;
        int ans = 0;
        int []sum = new int[n + 1];
        //System.out.print("0,");
        for (int i = 1; i <= n; i++) {

            sum[i] = sum[i - 1] + A[i - 1];
            System.out.print(sum[i] + ",");
        }
        //System.out.println("");

        for (int i = 1; i <= n; i++) {
            if (sum[i] >= start && sum[i] <= end) {
                ans++;
            }

            int max = sum[i] - start;
            int min = sum[i] - end;
            // System.out.println(sum[i] + " : " + max + " : " + min);
            // System.out.println(sum[i] + " : " + binarySearch(sum, max) + " : " + binarySearch(sum, min));
            ans += binarySearch(sum, max) - binarySearch(sum, min - 1);
        }
        return ans;
    }

    public int binarySearch(int[] sum, int value) {
        if (value <= 0 || value >= sum[sum.length - 1]) {
            return 0;
        }

        int start = 0;
        int end = sum.length - 1;

        while (end - start > 1) {
            int mid = start + (end - start) / 2;
            if (sum[mid] <= value) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (sum[end] <= value) {
            return end;
        } 
        return start;
    }
}