题目 #

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1

Constraints:

• $1 <= nums.length <= 10^5$
• $-2^{31} <= nums[i] <= 2^{31} - 1$
• $-10^5 <= lower <= upper <= 10^5$
• The answer is guaranteed to fit in a 32-bit integer.

思路1 线段树 #

分析 #

• 先把问题转化一下，求某个区间和，使用前缀和进行简化。区间和变成端点之间的差，问题转化为对于固定右端点j，在[0, j)之间找符合lower <= preSum[j]-preSum[i] <= upper
• 转成，在[0, j)找preSum[j]-upper <= preSum[i] <= preSum[j]-lower的数量

代码 #

 1func min(a, b int) int {
 2	if a > b {
 3		return b
 4	}
 5	return a
 6}
 7
 8func paintWalls(cost []int, time []int) int {
 9	n := len(cost)
10
11	mMap := make([]map[int]int, n)
12	for i := range mMap {
13		mMap[i] = make(map[int]int)
14	}
15	// 选和不选代价和时间花费不一样，可以认为付费的时间和花费是正的，免费的时间是负的，花费为0
16	// 最终求得是时间不为负数的花费最小值
17	var dfs func(i, t int) int
18	dfs = func(i, t int) int {
19		if t > i {
20			return 0
21		}
22		if i < 0 {
23			return math.MaxInt / 2
24		}
25		if mMap[i][t] > 0 {
26			return mMap[i][t]
27		}
28		// 为当前免费和当前不免费的最小值
29		res := min(dfs(i-1, t-1), dfs(i-1, t+time[i])+cost[i])
30		mMap[i][t] = res
31		return res
32	}
33	return dfs(n-1, 0)
34}