除自身以外数组的乘积

怎样从“nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。”推导出 前缀积 · 除自身外乘积，并证明每次状态变化都不会漏掉答案？

中心结论：前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。

nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。

在本站主例中，nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。

算法最终需要得到或观察：ans[i]=除 i 外全体乘积。

每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“前缀累计仪”，明确答案需要观察什么。
2. 2状态只维护 prefix、suffix、结果数组。
3. 3转移每一步按照 前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。
4. 4收尾读取 ans[i]=除 i 外全体乘积。，并复核边界与复杂度。

把“某段区间”改写成“两个前缀之间的关系”。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：prefix、suffix、结果数组。

前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。

执行过程中持续维护：prefix、suffix、结果数组。

正确性依赖以下不变量：ans[i]=prefix[i-1]*suffix[i+1]。

面试时可以压缩为：两次扫描 prefix/suffix O(n)/O(1) 额外。

落到当前题，执行机制可以压缩为：前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。 因为：前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。
2. 2prefix[1] = prefix[0] × nums[0] = 1记录左侧所有乘积。 因为：不含 nums[i] 自身。
3. 3prefix[2] = prefix[1] × nums[1] = 2记录左侧所有乘积。 因为：不含 nums[i] 自身。
4. 4prefix[3] = prefix[2] × nums[2] = 6记录左侧所有乘积。 因为：不含 nums[i] 自身。
5. 5ans[3] = prefix[3] × suffix = 6合并左右积。 因为：O(n) O(1) 额外空间(输出除外)。
6. 6ans[1] = prefix[1] × suffix = 12合并左右积。 因为：O(n) O(1) 额外空间(输出除外)。
7. 7ans[0] = prefix[0] × suffix = 24合并左右积。 因为：O(n) O(1) 额外空间(输出除外)。
8. 8收尾与复杂度ans[i]=除 i 外全体乘积。 因为：时间 O(n) · 空间 O(1)。前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// 解法一 前缀积 * 后缀积。不使用除法，时间复杂度 O(n)，除输出数组外空间复杂度 O(1)。
func productExceptSelf(nums []int) []int {
	n := len(nums)
	res := make([]int, n)
	// res[i] 先存 nums[i] 左边所有元素的乘积
	res[0] = 1
	for i := 1; i < n; i++ {
		res[i] = res[i-1] * nums[i-1]
	}
	// 再从右往左乘上 nums[i] 右边所有元素的乘积，right 累计后缀积
	right := 1
	for i := n - 1; i >= 0; i-- {
		res[i] *= right
		right *= nums[i]
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="product-except-self", nums=[1,2,3,4]
    //    期望：ans[i]=除 i 外全体乘积。
    //
    // 2. 失败 / 未命中
    //    检查：直接用除法遇 0 麻烦且题目可能限制。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC42 接雨水；LC560 和为 K
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意nums=[1,2,3,4],输出 [24,12,8,6] 不用除法。
2. 2重复每次重新计算区间会重复累加；前缀状态把区间信息变成两个历史状态的差或关系。
3. 3优化前缀积+后缀积;或输出数组当前缀再倒序乘后缀 O(1) 空间。
4. 4证明ans[i]=prefix[i-1]*suffix[i+1]。
5. 5复杂度时间 O(n)，空间 O(1)