题目描述
用例说明
思路讲解
看到对某一区间内进行求和，很容易想到前缀和
定义一个sums数组用于存储前缀和，容量为nums.length+1
初始化的时候对nums数组进行求和，将前k项的和存储进sums数组中
这样对某一区间[left,right]的求和就不必遍历一遍，直接返回sums[right+1]-sums[left]即可
将原本可能会有的O(n)（n为数组nums的长度）复杂度降到了常数级复杂度
代码
class NumArray {
int[] sums;
public NumArray(int[] nums) {
sums=new int[nums.length+1];
for(int i=0;i<nums.length;i++){
sums[i+1]=sums[i]+nums[i];
}
}
public int sumRange(int left, int right) {
return sums[right+1]-sums[left];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(left,right);
*/复杂度
时间复杂度：初始化需要遍历一遍数组O(n)，每次查找区间和O(1)
空间复杂度：O(n)
