题目
思路
通过 O(n) 维护一个前缀和数组,通过 O(1)查询区间和
代码
class NumArray {
public:
vector<int> sum;
NumArray(vector<int>& nums) {
int n = nums.size();
sum = vector<int>(n + 1, 0);
for (int i=1;i<=n;++i) sum[i] = sum[i-1] + nums[i-1];
}
int sumRange(int i, int j) {
return sum[j+1] - sum[i];
}
};
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-303-range-sum-query-immutable/
[…] 小旭讲解 LeetCode 303. 区域和检索 – 数组不可变 […]