题目地址：

https://www.lintcode.com/problem/subarray-sum-ii/description

给定一个正整数数组$A$，再给定一个区间$[s,e]$，问$A$有多少个子数组之和位于那个区间内。

思路是前缀和。先把$A$的前缀和$p$算出来，其中$p[i]={\sum }_{k=0}^{i-1}A[k]$，规定$p[0]=0$。对于$i<j$，就对应了一个子数组的和，如果$e\ge p[j]-p[i]\ge s$，可以枚举$j$，则$p[j]-s\ge p[i]\ge p[j]-e$。由于$A$恒正，所以$p$是严格单调增的，所以可以用二分的方式搜索出$i$的范围。代码如下：

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 // 求前缀和 int[] preSum = new int[A.length + 1]; for (int i = 0; i < A.length; i++) { preSum[i + 1] = preSum[i] + A[i]; } // 统计答案 int res = 0; for (int i = 1; i < preSum.length; i++) { int left = 0, right = 0; // 找第一个大于等于target的数的下标 int target = preSum[i] - end; int l = 0, r = i - 1; while (l < r) { int m = l + (r - l >> 1); if (preSum[m] >= target) { r = m; } else { l = m + 1; } } if (preSum[l] < target) { continue; } else { left = l; } // 找最后一个小于等于target的数的下标 l = 0; r = i - 1; target = preSum[i] - start; while (l < r) { int m = l + (r - l + 1 >> 1); if (preSum[m] <= target) { l = m; } else { r = m - 1; } } if (preSum[l] > target) { continue; } else { right = l; } // 两个都找到了，累加个数 res += right - left + 1; } return res; } }

时间复杂度$O(n\log n)$，空间$O(n)$。