区域和检索-数组不可变
该题目最简单想的一定是存储数组，然后每次调用算法时，遍历相加即可，但是有一个问题，缺少对计算结果的记录，导致每次都得重新计算，这会降低效率，所以改进便是通过将每个索引的前缀和计算保存，这样就不需要每次都计算求和，而是进行索引和相减即可，这样通过一次求和记录，使得未来调用不用重复计算求和，降低了时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class NumArray {
public int [] arr;
public NumArray(int[] nums) {
arr = new int[nums.length];
for(int i =0;i<nums.length;i++){
if(i==0){
arr[i] = nums[i];
}else{
arr[i] = arr[i-1]+nums[i];
}
}
}
public int sumRange(int left, int right) {
if(left==0){
return arr[right];
}else{
return arr[right]-arr[left-1];
}
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(left,right);
*/
|
