区域和检索 - 数组不可变

题目：

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

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 说明:

你可以假设数组不可变。会多次调用 sumRange 方法。

解题思路：

我们可以提前计算出前 i 个数的和，即 a[i] 等于区间 [1,i] 的和，消耗时间为 O(n)

区间 [i,j] 的和求公式为：SumRange(i,j) = sum[j] - sum[i-1]，每次查询消耗时间为 O(1)，k 次查询时间复杂度为 O(k)

总的来说，时间复杂度为 O(n+k)

当然，这里用了数组来存储和的结果，自然多消耗了空间。这里空间复杂度为 O(n)。一般而言，很多优化都是以空间换时间。

// go
type NumArray struct {
 sum []int // 存储[0,i]的和
}

func Constructor(nums []int) NumArray {
 a := NumArray{}
 a.sum = append(a.sum, 0) // 初始化 sum 切片，sum[0]=0
  // 遍历求sum[i]
 for i := 1; i <= len(nums); i++ {
  a.sum = append(a.sum, a.sum[i-1]+nums[i-1])
 }
 return a
}

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

区域和检索 - 数组不可变

原文：https://www.cnblogs.com/smallleiit/p/13246796.html