此题目可以用一个数组preSum求前缀和,
preSum[i + 1] = preSum[i] + num[i]
preSum[i + 1]即为num[0, i]的和。
那么[i, j]之间的和即为preSum[j + 1] - preSum[i]
由于题目会多次调用sumRange方法,所以如果把求和放在sumRange方法中会浪费大量时间,如果在建立数组时就求出preSum数组则可以省下很多时间。
class NumArray {
public:
vector<int> pre;
NumArray(vector<int>& nums) {
if (nums.empty()) return ;
pre.resize(nums.size() + 1);
for (int i = 0; i < nums.size(); i++) {
pre[i + 1] = pre[i] + nums[i];
}
}
int sumRange(int i, int j) {
return pre[j + 1] - pre[i];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/