Example 1:

Input: A = [1, 2, 3, 4], start = 1, end = 3

Output: 4

Explanation: All possible subarrays: [1](sum = 1), [1, 2](sum = 3), [2](sum = 2), [3](sum = 3).

Example 2:

Input: A = [1, 2, 3, 4], start = 1, end = 100

Output: 10

Explanation: Any subarray is ok.
思路：

O(N) 的两根指针的算法

其实需要三根指针, 因为需要额外记录一下从哪个位置开始的加和已经 >= start 了.

对于每一个左端点 left, 求出对应的两个右端点 right_start, right_end. 前者表示最左边的使得 [left, right_start] 子数组的和不小于 start 的点, 而后者表示最右边的使得 [left, right_end] 子数组的和不大于 end 的点.

right_end - right_start + 1 就是以 left 为左端点的合法子数组的数量.

从左到右枚举 left, 而 right_start, right_end 随着left的增长也是只增不减的, 所以时间复杂度是 O(N)

O(NlogN) 的二分法

求出一个前缀和数组, 然后对于每一个前缀和 presum[right], 我们要求出两个点 left_start, left_end. 前者表示最左边的使得 [left_start, right] 子数组和不大于 end 的点, 后者表示最右边的使得 [left_end, right] 子数组和不小于 start 的点.

枚举 right, 我们可以在 presum[0..right] 上二分查找确定 left_start, left_end.

总结

上面两种方法是相通的, 都是对于子数组的一个端点, 确认另外一个端点的范围. 在枚举其中一个端点的过程, 另外一个端点的范围是单调的, 所以可以使用两根指针 O(N) 地完成.

可以把两根指针和二分法综合一下, 不过这样理论时间复杂度是不变的, 没有很大的必要. 以上两种方法推荐第一种, 复杂度更低.

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) {

        int n = A.length;

        if (n == 0) {

            return 0;

        }

        int[] sum = new int[n + 1];

        int i, l, r, res = 0;

        sum[0] = 0;

        for (i = 1; i <= n; ++i) {

            sum[i] = sum[i - 1] + A[i - 1];

        }

        l = r = 0;

        for (i = 1; i <= n; ++i) {

            while (l < i && sum[i] - sum[l] > end) {

                ++l;

            }

            while (r < i && sum[i] - sum[r] >= start) {

                ++r;

            }

            res += r - l;

        }

        return res;

    }

}