-
Notifications
You must be signed in to change notification settings - Fork 21
Expand file tree
/
Copy pathrangeSumQuery.java
More file actions
26 lines (23 loc) · 903 Bytes
/
Copy pathrangeSumQuery.java
File metadata and controls
26 lines (23 loc) · 903 Bytes
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
/* Approach is accumulate sum to each number index.
* The range sum from [i, j], is essentially the same as acccumulatedSum[j] - accumulateSum[i-1] */
public class NumArray {
private int[] sum;
public NumArray(int[] nums) {
if(nums.length > 0){
sum = new int[nums.length];
/* create a sum[] to accumulate sum to each index */
sum[0] = nums[0];
for(int i = 1; i < nums.length; i++){
sum[i] = nums[i] + sum[i -1]; /* accumulate step */
}
}
}
public int sumRange(int i, int j) {
/* need to check i == 0, in case sum[i-1] out of bound */
return i == 0 ? sum[j] : sum[j] - sum[i -1]; /* calculating range */
}
}
// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);