66. 构建乘积数组.md

解题思路

动态规划

使用两个 dp 一个 dp 构建左边累乘 一个 dp 构建右边累乘

func constructArr(a []int) []int {
    if len(a) == 0 {
        return a
    }
    // 初始化左边累乘
    l := make([]int, len(a))
    l[0] = 1
    for i := 1; i < len(a); i++ {
        l[i] = l[i-1] * a[i-1]
    }
    // 初始化右边累乘
    r := make([]int, len(a))
    r[len(r)-1] = 1
    for i := len(a)-2; i >= 0; i-- {
        r[i] = r[i+1] * a[i+1]
    }
    // dp[i] = l[i] * r[i]
    ans := make([]int, 0)
    for i := range a {
        ans = append(ans, l[i] * r[i])
    }
    return ans
}