区域和检索 - 数组不可变

[yankewei]

给定一个整数数组nums，求出数组从索引i到j（i ≤ j）范围内元素的总和，包含 i、j两点。

实现NumArray类： NumArray(int[] nums)使用数组nums初始化对象 int sumRange(int i, int j)返回数组nums从索引i到j（i ≤ j）范围内元素的总和，包含i、j两点（也就是sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

• 0 <= nums.length <= 104
• -105 <= nums[i] <= 105
• 0 <= i <= j < nums.length
• 最多调用 104 次 sumRange 方法

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/range-sum-query-immutable 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

暴力

每次查询的时候计算即可

type NumArray struct {
    nums []int
}

func Constructor(nums []int) NumArray {
    return NumArray{nums: nums}
}

func (this *NumArray) SumRange(i int, j int) int {
    var ans int
    for index := i; index <= j; index++ {
        ans += this.nums[index]
    }
    return ans
}

前缀和

type NumArray struct {
    sums []int
}

func Constructor(nums []int) NumArray {
    sums := make([]int, len(nums)+1)
    for i, v := range nums {
        sums[i+1] = sums[i] + v
    }
    return NumArray{sums}
}

func (na *NumArray) SumRange(i, j int) int {
    return na.sums[j+1] - na.sums[i]
}