一、问题直接转化为前缀和模型
1. 左右前缀积拆分
在处理数组乘积类问题时，如果要求不能使用除法且时间复杂度需控制在 O(n)，我们可以将整体拆分为左前缀积和右前缀积两部分。
以 LeetCode 238 题为例，给定整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。题目保证结果在 32 位整数范围内。
示例：
- 输入：
[1,2,3,4] - 输出：
[24,12,8,6]
思路是将每个位置的乘积分解为左侧所有元素乘积与右侧所有元素乘积的乘积。我们不需要显式地计算整个数组的总乘积再除以当前元素（因为涉及除法且可能有零），而是分别维护两个辅助数组：一个记录当前位置左侧的累积乘积，另一个记录右侧的累积乘积。
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] f = new int[n]; // 左侧前缀积
int[] g = new int[n]; // 右侧前缀积
int[] ret = new int[n];
f[0] = 1;
g[n - 1] = 1;
// 计算左侧前缀积
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] * nums[i - 1];
}
// 计算右侧前缀积
for (int i = n - 2; i >= 0; i--) {
g[i] = g[i + 1] * nums[i + 1];
}
( ; i < n; i++) {
ret[i] = f[i] * g[i];
}
ret;
}
