66. 构建乘积数组

题目链接

牛客

力扣

题目描述

给定一个数组 A[0, 1,..., n-1]，请构建一个数组 B[0, 1,..., n-1]，其中 B 中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。要求不能使用除法。

解题思路

保存两个数组，第一个为从左到右依次相乘的结果，第二个为从右到左依次相乘的结果 遍历生成数组的时候分别去左右两边对应位置的结果相乘

func constructArr(a []int) []int {
    size := len(a)
    if size == 0 {
        return nil
    }
    left, right := make([]int, size), make([]int, size)
    // generate left, right
    tmp := 1
    for i:=0; i<size; i++ {
        left[i] = tmp * a[i]
        tmp *= a[i]
    }

    tmp = 1
    idx := 0
    for i:=size-1; i>=0; i-- {
        right[idx] = tmp * a[i]
        tmp *= a[i]
        idx++
    }
    // fmt.Println(left, right)

    b := make([]int, size)
    for i:=0; i < size; i++ {
        if i == 0 {
            b[i] = right[size-2-i]
        } else if i == size - 1 {
            b[i] = left[i-1]
        } else {
            b[i] = left[i-1] * right[size-2-i]
        }
    }
    return b
}