除自身以外数组的乘积 图解题解

这道题真正在问什么

给数组 nums，返回同长数组 answer，answer[i] 等于除 nums[i] 之外所有元素的乘积，比如 [1,2,3,4] 的答案是 [24,12,8,6]。题目附加两条硬约束：不许用除法、时间必须 O(n)。这两条约束就是解法的路标——它们把最省事的那条路堵死，逼你去找乘法本身的结构。

为什么全积除以自己走不通

最诱人的做法是先算全体乘积 total，再让每个位置等于 total / nums[i]，一遍就完。但题目明说禁止除法；就算允许，这条路也有真实的坑：数组里只要有一个 0，total 就是 0，所有非零位置都会被算成 0；有两个以上 0 时更是全盘皆 0，必须层层特判。除法方案的脆弱反过来提示我们：得直接「凑」出其余元素的积，而不是「除」出来。

关键观察：答案等于左积乘右积

位置 i 除自身以外的元素，天然分成两段：i 左边的所有数、i 右边的所有数。所以 answer[i] 就等于左边一段的积乘以右边一段的积。而「左边一段的积」正是经典的前缀积，从左到右用一个变量一路累乘就能递推出来；「右边一段的积」对称地是后缀积，从右到左递推。两个方向各扫一遍，每个位置的两块拼图就都齐了。边界也很自然：最左位置左边没有数，约定空积为 1，最右位置同理。

为什么两遍扫描只要 O(1) 额外空间

直接开两个数组分别存前缀积和后缀积也能对，但要 O(n) 额外空间。省法是把答案数组本身当工作区：第一遍从左到右维护变量 prefix，先把 prefix 写进 answer[i]，再让 prefix 乘上 nums[i]——「先写后乘」的顺序保证写进去的恰好是不含自己的左积。

第二遍从右到左，用变量 suffix 同样先乘进 answer[i]、再累乘 nums[i]。两遍的不变量一致：走到位置 i 时，prefix（或 suffix）恰好等于 i 左边（或右边）全部元素的积。第二遍方向绝不能又从左往右——方向反了，suffix 积累的就不是右边的数，结果整体错位。

复杂度与容易踩的坑

时间 O(n)：两遍线性扫描，总共约 2n 次乘法。额外空间 O(1)：按惯例输出数组不计入，全程只多用 prefix、suffix 两个标量。最常见的三个错：偷偷用除法（数组含 0 就炸）、第二遍方向写反、以及把「先写答案再累乘」的顺序颠倒，把当前位置自己也乘了进去。

Python

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    prefix = 1                 # 左边所有数的积
    for i in range(n):         # 第一遍：从左到右
        answer[i] = prefix     # 先存左前缀积
        prefix *= nums[i]
    suffix = 1                 # 右边所有数的积
    for i in range(n - 1, -1, -1):  # 第二遍：从右到左
        answer[i] *= suffix    # 再乘右后缀积
        suffix *= nums[i]
    return answer

C++

vector<int> productExceptSelf(vector<int>& nums){
    int n = nums.size();
    vector<int> answer(n, 1);
    long prefix = 1;                 // 左边所有数的积
    for(int i = 0; i < n; i++){      // 第一遍：从左到右
        answer[i] = prefix;          // 先存左前缀积
        prefix *= nums[i];
    }
    long suffix = 1;                 // 右边所有数的积
    for(int i = n - 1; i >= 0; i--){ // 第二遍：从右到左
        answer[i] *= suffix;         // 再乘右后缀积
        suffix *= nums[i];
    }
    return answer;
}

Java

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    int prefix = 1;                 // 左边所有数的积
    for (int i = 0; i < n; i++) {   // 第一遍：从左到右
        answer[i] = prefix;         // 先存左前缀积
        prefix *= nums[i];
    }
    int suffix = 1;                 // 右边所有数的积
    for (int i = n - 1; i >= 0; i--) {  // 第二遍：从右到左
        answer[i] *= suffix;        // 再乘右后缀积
        suffix *= nums[i];
    }
    return answer;
}