Leetcode 303 Range Sum Query - Immutable
题意
前缀和模版题，初始化前缀和数组并且求下标从left到right的元素和
题目链接
https://leetcode.com/problems/range-sum-query-immutable/description/
题解
class NumArray {
public:
vector<int> preSum;
NumArray(vector<int>& nums) {
int n = nums.size();
preSum.resize(n+1, 0);
for(int i = 0; i < n; i++) {
preSum[i+1] = preSum[i] + nums[i];
}
}
int sumRange(int left, int right) {
return preSum[right+1] - preSum[left];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(left,right);
*/
时间复杂度
O
(
n
)
O(n)
O(n)
空间复杂度
O
(
n
)
O(n)
O(n)