Problem

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:

Solution: Prefix sum

sums[i] = nums[0] + nums[1] + … + nums[i]

sumRange(i, j) = sums[j] – sums[i – 1]

Time complexity: pre-compute: O(n), query: O(1)

Space complexity: O(n)

// Author: Huahua

// Running time: 112 ms

class NumArray {

public:

NumArray(vector<int> nums): sums_(nums) {

if (nums.empty()) return;

for (int i = 1; i < nums.size();++i)

sums_[i] += sums_[i - 1];

}

int sumRange(int i, int j) {

if (i == 0) return sums_[j];

return sums_[j] - sums_[i-1];

}

private:

vector<int> sums_;

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏