区域和检索-数组不可变
题目
给定一个整数数组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
说明:
你可以假设数组不可变。
会多次调用sumRange方法。
思路
设计一个类吧.可以从简单的来,然后一点点来优化.最开始我们只需要在内部保存一个int数组,然后赋值,然后每次计算返回即可.
优化的话最开始考虑存储所有的计算结果,但是内存肯定会超过.因此不能存储所有的计算结果.那可以存储所有的和的结果.然后每次sumRange就只需要减差值就好了.存储和的结果时可以使用动态规划来避免重复计算的问题
代码
最简单代码
class NumArray {
private int[] localNums;
public NumArray(int[] nums) {
localNums = nums;
}
public int sumRange(int i, int j) {
int sum = 0;
if(i < 0 || j > localNums.length){
throw new RuntimeException();
}
for(;i <= j;i++){
sum+=localNums[i];
}
return sum;
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
使用动态规划和存储数组的和来解决
class NumArray {
private int[] sum = null;
public NumArray(int[] nums) {
if(nums != null && nums.length != 0){
sum = new int[nums.length];
sum[0] = nums[0];
for(int i = 1 ; i < nums.length ; i ++)
sum[i] = sum[i-1] + nums[i];
}
}
public int sumRange(int i, int j) {
int a = (i > 0 ? sum[i-1] : 0);
int b = sum[j];
return b - a;
}
}
