LeetCode -- Range Sum Query - Immutable
题目描述
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
传入起始索引，返回数组求和的值。
思路：
使用缓存前n项的和。
public class NumArray {
private int[] _cacheSum ;
private int[] _nums;
public NumArray(int[] nums) {
_nums = nums;
_cacheSum = new int[nums.Length];
var s = 0;
for (var i = 0;i < nums.Length; i++){
s += nums[i];
_cacheSum[i] = s;
}
}
public int SumRange(int i, int j) {
if(_nums == null || _nums.Length == 0){
return 0;
}
if(i < 0 || j > _nums.Length - 1){
return 0;
}
return _cacheSum[j] - _cacheSum[i] + _nums[i];
}
}