303. 区域和检索 - 数组不可变
image.png
解题思路
典型的前缀和题目
- 根据nums计算前缀和数组，添加辅助位，方便后续操作。（编码注意点见下）
- 计算区间，因为加了辅助位。
sum[j+1]= nums[0] + nums[1] + ... + nums[j],sum[i] = nums[0] + nums[1] + ... + nums[i-1].所以sum[j+1]-sum[i]= nums[i]+...nums[j].为区间和
前缀和编码注意点
笔者每次在解前缀和的时候手速都不快，每次都要想很久。这次总结下主要是边界这边思考不清楚。
为了防止数组越界，可以选择添加一个辅助位。
则有定义如下:
sum[i] = nums[0] + nums[1] + ... + nums[i-1]
即sum[i]标志为 nums数组中下标小于i的所有数字的和。
则计算区间[i,j],则可以用 sum[j+1]-sum[i]表示。
代码
type NumArray struct {
Sum []int
// nums []int
}
func Constructor(nums []int) NumArray {
sum := make([]int,len(nums)+1)
for i:=1;i<len(sum);i++{
sum[i]=sum[i-1]+ nums[i-1]
}
return NumArray{
// nums:nums,
Sum:sum,
}
}
func (this *NumArray) SumRange(i int, j int) int {
return this.Sum[j+1]-this.Sum[i]
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(i,j);
*/
