leetcode 前缀和-题集_leecode 前缀和习题

560. 和为 K 的子数组

func subarraySum(nums []int, k int) int {
    cnt := 0
    n := len(nums)
    for i := 0; i < n; i++ {
        sum := 0
        for j := i; j < n; j++ {
            sum += nums[j]
            if sum == k {
                cnt++
            }
        }
    }
    return cnt
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

type NumArray struct {
    preSums []int
}


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


func (this *NumArray) SumRange(left int, right int) int {
    return this.preSums[right+1] - this.preSums[left]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

304. 二维区域和检索 - 矩阵不可变

type NumMatrix struct {
    nums [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    m, n := len(matrix), len(matrix[0])
    nums := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        nums[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <=n; j++ {
            nums[i][j] =nums[i-1][j] + nums[i][j-1] - nums[i-1][j-1] + matrix[i-1][j-1]
        }
    }
    return NumMatrix{nums}
}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.nums[row2+1][col2+1] - this.nums[row1][col2+1] - this.nums[row2+1][col1] + this.nums[row1][col1]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

724. 寻找数组的中心下标

func pivotIndex(nums []int) int {
    var sum int
    n := len(nums)
    preSums := make([]int, n+1)
    // 计算前缀和
    for i := 1; i <= n; i++ {
        sum += nums[i-1]
        preSums[i] = sum
    }

    for i := 0; i < n; i++ {
        if preSums[i] == preSums[n] - preSums[i+1] {
            return i
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17