Given an integer arraynums, find the sum of the elements between indicesiandj(i≤j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
题目非常简单,所以最暴力的方法就是从数组i位置开始累加到j位置,但是这样会超时。
优化后的方法是:遍历nums,每个元素的位置存储的值是此元素之前的所有元素值之和。当计算i与j之间的元素和时,只需要用j位置的元素和减去i-1位置的元素和,并且注意考虑边界条件
public class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
for(int i = 1; i < this.nums.length; i++){
this.nums[i] += this.nums[i-1];
}
}
public int sumRange(int i, int j) {
if(i > j)
return -1;
else if(i == 0)
return this.nums[j];
else
return this.nums[j] - this.nums[i-1];
}
}```
/**
- Your NumArray object will be instantiated and called as such:
- NumArray obj = new NumArray(nums);
- int param_1 = obj.sumRange(i,j);
*/```