题目大意
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明：
1.你可以假设数组不可变。
2.会多次调用 sumRange 方法。
方法一：暴力法
直接遍历i到j的数组，计算sum。
private int[] data;
public NumArray(int[] nums) {
data = nums;
}
public int sumRange(int i, int j) {
int sum = 0;
for (;i<=j;i++)
sum+=data[i];
return sum;
}
运行时间551ms,击败7.06%。
方法二：动态规划
sum[k]表示下标0...k-1的序列和。
private int[] data;
private int[] sum;
public NumArray(int[] nums) {
data = nums;
sum = new int[nums.length+1];
for(int i=0;i<nums.length;i++)
sum[i+1]=sum[i]+nums[i];
}
public int sumRange(int i,int j) {
return sum[j+1]-sum[i];
}
注意：这里有个技巧是设置一个虚拟0，避免一些越界操作。
