题目描述 给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。 说明:最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。 示例: 输入: nums = [-2,5,-1], lower = -2, upper = 2, 输出: 3 解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。 https://leetcode-cn.com/problems/count-of-range-sum/ 解法1 先解释下naive的做法，为了计算区间和，一般来说prefix sum是少不了的。有了prefix sum，我们可以在O(1)的时间计算出区间和。首先定义一个数组preSum[i] = sum(nums[0]…nums[i])。然后我们计算符合lower<=preSum[j] – preSum[i]<=upper的次数。显然，这种做法的时间复杂度是O(n^2)。 解法1采用merge sort。我们回忆“315.计算右侧小于当前元素的个数”，我们将题目的目标形式化定义： counts[i] = 统计 nums[i] < nums[j] 成立的次数，0 <= i < j < n 在那道题中，我们将nums进行merge sort，在merge的过程时，用rightCount变量统计nums[i] > nums[j]的次数，当下一次nums[i]…