Week 6 @ 2025 算法周记【前缀和 + 滑动窗口】

1 前缀和
- 1.1 LC 1314. 矩阵区域和
- 1.2 LC 724. 寻找数组的中心下标
2 前缀积
- 2.1 LC 238. 除自身以外数组的乘积
- 2.2 LC 1352. 最后 K 个数的乘积
3 滑动窗口
- 3.1 LC 1658. 将 x 减到 0 的最小操作数
- 3.2 LC 713. 乘积小于 K 的子数组

前缀和

LC 1314. 矩阵区域和

https://leetcode.com/problems/matrix-block-sum/

func matrixBlockSum(mat [][]int, k int) [][]int {
    m, n := len(mat), len(mat[0])
    sums := getSumsArray(mat)

    getI := func(i int) int {
        if i <= 0 {
            return 0
        } else if i >= m-1 {
            return m-1
        } else {
            return i
        }
    }
    getJ := func(j int) int {
        if j <= 0 {
            return 0
        } else if j >= n-1 {
            return n-1
        } else {
            return j
        }
    }

    getRangeSum := func(T, B, L, R int) int {
        safe := func(i, j int) int {
            if i < 0 || j < 0 {
                return 0
            } 
            
            return sums[i][j]
        }

        return sums[B][R] - safe(B, L-1) - safe(T-1, R) + safe(T-1, L-1)
    }

    result := new2dArray(m, n)

    for i := 0; i < m; i++ {
        T, B := getI(i-k), getI(i+k)
        for j := 0; j < n; j++ {
            L, R := getJ(j-k), getJ(j+k)

            result[i][j] = getRangeSum(T, B, L, R)
        }
    }

    return result
}

func new2dArray(m, n int) [][]int {
    arr := make([][]int, m)
    for i := range arr {
        arr[i] = make([]int, n)
    }
    return arr
}

func getSumsArray(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])

    sums := new2dArray(m, n)

    sums[0][0] = mat[0][0]
    for j := 1; j < n; j++ {
        sums[0][j] = sums[0][j-1] + mat[0][j]
    }
    for i := 1; i < m; i++ {
        sums[i][0] = sums[i-1][0] + mat[i][0]
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + mat[i][j]
        }
    }

    return sums
}

LC 724. 寻找数组的中心下标

https://leetcode.com/problems/find-pivot-index/description/

func pivotIndex(nums []int) int {
    n := len(nums)
    leftSum := make([]int, n+1)
    for i := range nums {
        leftSum[i+1] = leftSum[i] + nums[i]
    }
    rightSum := make([]int, n+1)
    for i := n - 1; i >= 0; i-- {
        rightSum[i] = rightSum[i+1] + nums[i]
    }

    for i := range nums {
        if leftSum[i] == rightSum[i+1] {
            return i
        }
    }

    return -1
}

只使用前缀和（不计算后缀和）

func pivotIndex(nums []int) int {
    n := len(nums)
    leftSum := make([]int, n+1)
    totalSum := 0
    for i, v := range nums {
        leftSum[i+1] = leftSum[i] + v
        totalSum += v
    }
    
    for i, v := range nums {
        if leftSum[i] == totalSum - leftSum[i] - v {
            return i
        }
    }

    return -1
}

前缀积

LC 238. 除自身以外数组的乘积

https://leetcode.com/problems/product-of-array-except-self/description/

func productExceptSelf(nums []int) []int {
    n := len(nums)

    preProduct := make([]int, n+1)
    preProduct[0] = 1
    for i, v := range nums {
        preProduct[i+1] = preProduct[i] * v
    }

    postProduct := make([]int, n+1)
    postProduct[n] = 1
    for i := n-1; i >= 0; i-- {
        postProduct[i] = postProduct[i+1] * nums[i]
    }

    results := make([]int, n)

    for i := range nums {
        results[i] = preProduct[i] * postProduct[i+1]
    }

    return results
}

不使用额外空间

func productExceptSelf(nums []int) []int {
    n := len(nums)

    result := make([]int, n)
    result[0] = 1

    v := 1
    for i := 1; i < len(nums); i++ {
        v *= nums[i-1]
        result[i] = v
    }

    v = 1
    for i := len(nums) - 2; i >= 0; i-- {
        v *= nums[i+1]
        result[i] *= v
    }

    return result
}

LC 1352. 最后 K 个数的乘积

https://leetcode.com/problems/product-of-the-last-k-numbers/description/

type ProductOfNumbers struct {
    products []int
}


func Constructor() ProductOfNumbers {
    return ProductOfNumbers{
        products: []int{1},
    }
}


func (this *ProductOfNumbers) Add(num int)  {
    if num == 0 {
        this.products = []int{1}
        return
    }

    this.products = append(this.products, this.products[len(this.products)-1] * num)
}


func (this *ProductOfNumbers) GetProduct(k int) int {
    n := len(this.products)

    if n-1 < k {
        return 0
    }

    return this.products[n-1] / this.products[n-k-1]
}


/**
 * Your ProductOfNumbers object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(num);
 * param_2 := obj.GetProduct(k);
 */

滑动窗口

LC 1658. 将 x 减到 0 的最小操作数

https://leetcode.com/problems/minimum-operations-to-reduce-x-to-zero/

dfs（超时）

func minOperations(nums []int, x int) int {
    v := dfs(nums, x)

    if v >= MAX {
        return -1
    } else {
        return v
    }
}

func dfs(nums []int, x int) int {
    if x == 0 {
        return 0
    }
    if len(nums) == 1 {
        if nums[0] == x {
            return 1
        } else {
            return MAX
        }
    }

    v := MAX
    if nums[0] <= x {
        v = dfs(nums[1:], x-nums[0]) + 1
    }
    if nums[len(nums)-1] <= x {
        v = min(
            v,
            dfs(nums[:len(nums)-1], x-nums[len(nums)-1]) + 1,
        )
    }

    return v
}

const MAX = 1_000_000_001

dfs + 记忆化数组（OOM）

func minOperations(nums []int, x int) int {
    mem := newMatrix(len(nums))
    v := dfs(nums, x, 0, len(nums)-1, mem)

    if v >= MAX {
        return -1
    } else {
        return v
    }
}

func dfs(nums []int, x int, i, j int, mem [][]int) int {
    if x == 0 {
        return 0
    }
    if i > j {
        return MAX
    }
    if i == j {
        if nums[i] == x {
            return 1
        } else {
            return MAX
        }
    }

    v := MAX

    if mem[i][j] != 0 {
        return mem[i][j]
    }
    defer func() {
        mem[i][j] = v
    }()

    if nums[i] <= x {
        v = dfs(nums, x-nums[i], i+1, j, mem) + 1
    }
    if nums[j] <= x {
        v = min(
            v,
            dfs(nums, x-nums[j], i, j-1, mem) + 1,
        )
    }

    return v
}

const MAX = 1_000_000_001

func newMatrix(n int) [][]int {
    m := make([][]int, n)
    for i := range m {
        m[i] = make([]int, n)
    }
    return m
}

滑动窗口（变换）

func minOperations(nums []int, x int) int {
    target := -x
    for _, v := range nums {
        target += v
    }

    l := -1
    i, j := 0, 0
    sum := 0
    for j < len(nums) {
        sum += nums[j]
        j++

        for i < j && sum > target {
            sum -= nums[i]
            i++
        }

        if sum == target {
            l = max(l, j-i)
        }
    }


    if l == -1 {
        return -1
    } else {
        return len(nums) - l
    }
}

const MAX = 100_005

LC 713. 乘积小于 K 的子数组

https://leetcode.com/problems/subarray-product-less-than-k/

func numSubarrayProductLessThanK(nums []int, k int) int {
    i, j := 0, 0
    product := 1
    count := 0

    for j < len(nums) {
        product *= nums[j]
        j++

        for i < j && product >= k {
            product /= nums[i]
            i++
        }

        n := j - i
        count += n
    }

    return count
}

知识库

Week 6 @ 2025 算法周记【前缀和 + 滑动窗口】

Analytics

前缀和

LC 1314. 矩阵区域和

LC 724. 寻找数组的中心下标

前缀积

LC 238. 除自身以外数组的乘积

LC 1352. 最后 K 个数的乘积

滑动窗口

LC 1658. 将 x 减到 0 的最小操作数

LC 713. 乘积小于 K 的子数组

Related content