Week 3 @ 2025 算法周记【前缀和 + 双指针数组】

type NumArray struct {
    sums []int
}


func Constructor(nums []int) NumArray {
    sums := make([]int, len(nums))
    sums[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        sums[i] = sums[i-1] + nums[i]
    }
    return NumArray{sums}
}


func (this *NumArray) SumRange(left int, right int) int {
    if left == 0 {
        return this.sums[right] 
    }
    
    return this.sums[right] - this.sums[left-1]
}


/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.SumRange(left,right);
 */

type NumMatrix struct {
    sums [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    sums := make([][]int, len(matrix)+1)
    sums[0] = make([]int, len(matrix[0])+1)
    for i := range matrix {
        sums[i+1] = make([]int, len(matrix[0])+1)

        for j := range matrix[i] {
            sums[i+1][j+1] = sums[i+1][j] + matrix[i][j]
        }
    }
    // fmt.Println(sums)
    for i := range matrix {
        for j := range matrix[i] {
            sums[i+1][j+1] += sums[i][j+1]
        }
    }

    // for i := range sums {
    //     for j := range sums[i] {
    //         fmt.Printf("%2d ", sums[i][j])
    //     }
    //     fmt.Println()
    // }

    return NumMatrix { sums }
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1]  +  this.sums[row1][col1]
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */