Range Sum Query - Immutable
思路:
动态规划，每次计算和的时候用上一次计算的结果。时间复杂度为O(n)。不用的话时间复杂度为O(n2). Table 方便查询
比如nums长度是n 查询m次 就是O(nm)
但是存一个NumArray[i]，表示从0－i的sum和，那么查询sum[i,j]即为sum[0,j] - sum[0,i]
Runtime Error
class NumArray {
int sum[];
public NumArray(int[] nums) {
int len = nums.length;
sum = new int[len];
sum[0] = nums[0];
for (int i = 1; i< len; i++){
sum[i] = sum[i-1] + nums[i];
}
}
public int sumRange(int i, int j) {
if(i < 0 || j >= sum.length || i >j )return 0;
if(i == 0) return sum[j];
else return sum[j]-sum[i-1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
看来查询nums也很占时间啊。。小小改动就accept了
class NumArray {
int sum[];
public NumArray(int[] nums) {
int len = nums.length;
sum = nums.clone();
for (int i = 1; i< len; i++){
sum[i] += sum[i-1];
}
}
public int sumRange(int i, int j) {
if(i < 0 || j >= sum.length || i >j )return 0;
if(i == 0) return sum[j];
else return sum[j]-sum[i-1];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
