LeetCode -- Range Sum Query - Immutable
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项的和。
题目描述
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];
}
}