题解

解法：前缀积 + 后缀积

• 维护两个数组：

  1. prefix[i]：nums[i] 左侧 所有元素的乘积。
  2. suffix[i]：nums[i] 右侧 所有元素的乘积。

• 最终结果

  ：

  • answer[i] = prefix[i] * suffix[i]。

计算方式

1. 计算 prefix 数组

   ：

   prefix[0] = 1
   prefix[i] = prefix[i - 1] * nums[i - 1]
   

2. 计算 suffix 数组

   ：

   suffix[n-1] = 1
   suffix[i] = suffix[i + 1] * nums[i + 1]
   

3. 计算 answer[i] = prefix[i] \* suffix[i]。

时间 & 空间复杂度

• 时间复杂度：O(n)。
• 空间复杂度：O(1)（可以直接用 answer 存 prefix，然后再计算 suffix）。

代码实现

C++ 实现

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> answer(n, 1);

    // 计算前缀积
    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;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    vector<int> answer = productExceptSelf(nums);
    
    for (int i = 0; i < n; i++) {
        cout << answer[i] << " ";
    }
    cout << endl;

    return 0;
}

Python 实现

def product_except_self(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

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))

    result = product_except_self(nums)
    print(" ".join(map(str, result)))

Java 实现

import java.util.Scanner;

public class Main {
    public static 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;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        scanner.close();

        int[] result = productExceptSelf(nums);
        for (int num : result) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}

题目描述

给定一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

输入格式

• 第一行输入整数 n，表示数组 nums 的长度。
• 第二行输入 n 个整数，表示数组 nums 的元素。

输出格式

• 输出 n 个整数，表示 answer 数组。

输入样例

4
1 2 3 4

输出样例

24 12 8 6

输入 保证 数组 $answer[i]$在 32 位 整数范围内