力扣刷题系列-303. 区域和检索 - 数组不可变
题干题目分析代码实现
题干
原题链接
输入： [“NumArray”, “sumRange”, “sumRange”, “sumRange”] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出： [null, 1, -1, -3] 解释： NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3) numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
题目分析
本题运用到了前缀和算法，前缀和顾名思义就是数组前i个元素的累加和。通过预处理求出前缀和，对于求解区间类dp问题效果明显。比如本题中求解某一区间段(i,j)的累加和，dp[i]表示前i-1个元素的前缀和，即可通过dp[j+1]-dp[i]求出区间段(i,j)的累加和。本题的状态设计需要提前了解前缀和算法，算是本题的关键点
代码实现
class NumArray {
int[] sum
;
public NumArray(int[] nums
) {
sum
= new int[nums
.length
+ 1];
sum
[0] = 0;
for(int i
= 1; i
<= nums
.length
; ++i
){
sum
[i
] = sum
[i
- 1] + nums
[i
- 1];
}
}
public int sumRange(int i
, int j
) {
return sum
[j
+ 1] - sum
[i
];
}
