leetcode303 区域和检索 - 数组不可变 golang实现

303. 区域和检索 - 数组不可变

image.png

解题思路

典型的前缀和题目

1. 根据nums计算前缀和数组，添加辅助位，方便后续操作。（编码注意点见下）
2. 计算区间，因为加了辅助位。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);
 */

参考

1. https://oi-wiki.org/basic/prefix-sum/

有疑问加站长微信联系（非本文作者）