238. 除自身以外数组的乘积 - 已题解语言：Ruby/Python/Java/C++/JavaScript/C#/Go

LeetCode Python, Java, C++ > 数组 > 238. 除自身以外数组的乘积 > 已支持 Ruby, Python, Java, C++, JavaScript, C#, Go > GitHub 或转发

力扣链接：238. 除自身以外数组的乘积，难度等级：中等。

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

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]

输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]

输出: [0,0,9,0,0]

约束:

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
输入保证数组 answer[i] 在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

提示 1

Think how you can efficiently utilize prefix and suffix products to calculate the product of all elements except self for each index. Can you pre-compute the prefix and suffix products in linear time to avoid redundant calculations?

提示 2

Can you minimize additional space usage by reusing memory or modifying the input array to store intermediate results?

题解 1: 一维数组O(N)
题解 2: 滚动变量 O(1)

思路
上一题 下一题

分解问题：将"除自身外的乘积"分解为"左侧乘积 × 右侧乘积"
两次遍历：先计算每个元素的左侧乘积，再计算右侧乘积
合并结果：将左右乘积相乘得到最终结果

“预计算技术”的模式

预计算技术（Pre-Computation Techniques） 是一种通过提前计算并存储中间结果或常用数据，以减少实时计算开销的优化方法。其核心思想是“用空间换时间”。

主要应用场景

数组的前缀/后缀计算问题。
高频计算问题：如斐波那契数列、阶乘、素数表等，通过预先生成查找表（Lookup Table）避免重复计算。
动态规划（DP）：预先计算子问题的解并存储，如背包问题、最短路径问题。

步骤

初始化数组：
- 创建leftProducts数组，存储每个元素左侧所有元素的乘积
- 创建rightProducts数组，存储每个元素右侧所有元素的乘积
计算左侧乘积（从左到右遍历）：
- 第一个元素左侧乘积初始化为1
- 后续元素：leftProducts[i] = nums[i-1] * leftProducts[i-1]
计算右侧乘积（从右到左遍历）：
- 最后一个元素右侧乘积初始化为1
- 前序元素：rightProducts[i] = nums[i+1] * rightProducts[i+1]
合并结果：
- 遍历每个位置，将左右乘积相乘：answer[i] = leftProducts[i] * rightProducts[i]
返回结果数组

复杂度

时间复杂度

O(N)

空间复杂度

O(N)

Ruby #

# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
  #           nums: [1,  2, 3, 4]
  #  left_products: [1,  1, 2, 6]
  # right_products: [24,12, 4, 1]
  #         answer: [24,12, 8, 6]
  size = nums.size

  left_products = Array.new(size, 1)
  (1...size).each do |i|
    left_products[i] = nums[i - 1] * left_products[i - 1]
  end

  right_products = Array.new(size, 1)
  (size - 2).downto(0) do |i|
    right_products[i] = nums[i + 1] * right_products[i + 1]
  end

  answer = []
  (0...size).each do |i|
    answer << left_products[i] * right_products[i]
  end

  answer
end

Python #

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)

        #           nums: [1,  2, 3, 4]
        #  left_products: [1,  1, 2, 6]
        # right_products: [24,12, 4, 1]
        #         answer: [24,12, 8, 6]
        left_products = [1] * size
        for i in range(1, size):
            left_products[i] = nums[i - 1] * left_products[i - 1]

        right_products = [1] * size
        for i in range(size - 2, -1, -1):
            right_products[i] = nums[i + 1] * right_products[i + 1]

        answer = []
        for i in range(size):
            answer.append(left_products[i] * right_products[i])

        return answer

Java #

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        //           nums: [1,  2, 3, 4]
        //  left_products: [1,  1, 2, 6]
        // right_products: [24,12, 4, 1]
        //         answer: [24,12, 8, 6]
        int[] leftProducts = new int[size];
        leftProducts[0] = 1;
        for (int i = 1; i < size; i++) {
            leftProducts[i] = nums[i - 1] * leftProducts[i - 1];
        }

        int[] rightProducts = new int[size];
        rightProducts[size - 1] = 1;
        for (int i = size - 2; i >= 0; i--) {
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];
        }

        int[] answer = new int[size];
        for (int i = 0; i < size; i++) {
            answer[i] = leftProducts[i] * rightProducts[i];
        }

        return answer;
    }
}

C++ #

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        //           nums: [1,  2, 3, 4]
        //  left_products: [1,  1, 2, 6]
        // right_products: [24,12, 4, 1]
        //         answer: [24,12, 8, 6]
        vector<int> left_products(size, 1);
        for (int i = 1; i < size; i++) {
            left_products[i] = nums[i - 1] * left_products[i - 1];
        }

        vector<int> right_products(size, 1);
        for (int i = size - 2; i >= 0; i--) {
            right_products[i] = nums[i + 1] * right_products[i + 1];
        }

        vector<int> answer(size);
        for (int i = 0; i < size; i++) {
            answer[i] = left_products[i] * right_products[i];
        }

        return answer;
    }
};

JavaScript #

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
  const size = nums.length

  const leftProducts = new Array(size).fill(1)
  for (let i = 1; i < size; i++) {
    leftProducts[i] = nums[i - 1] * leftProducts[i - 1]
  }

  const rightProducts = new Array(size).fill(1)
  for (let i = size - 2; i >= 0; i--) {
    rightProducts[i] = nums[i + 1] * rightProducts[i + 1]
  }

  const answer = []
  for (let i = 0; i < size; i++) {
    answer.push(leftProducts[i] * rightProducts[i])
  }

  return answer
};

C# #

public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int size = nums.Length;
        //           nums: [1,  2, 3, 4]
        //  left_products: [1,  1, 2, 6]
        // right_products: [24,12, 4, 1]
        //         answer: [24,12, 8, 6]
        int[] leftProducts = new int[size];
        leftProducts[0] = 1;

        for (int i = 1; i < size; i++)
            leftProducts[i] = nums[i - 1] * leftProducts[i - 1];

        int[] rightProducts = new int[size];
        rightProducts[size - 1] = 1;

        for (int i = size - 2; i >= 0; i--)
            rightProducts[i] = nums[i + 1] * rightProducts[i + 1];

        int[] answer = new int[size];

        for (int i = 0; i < size; i++)
            answer[i] = leftProducts[i] * rightProducts[i];

        return answer;
    }
}

Go #

func productExceptSelf(nums []int) []int {
    size := len(nums)

    leftProducts := make([]int, size)
    leftProducts[0] = 1
    for i := 1; i < size; i++ {
        leftProducts[i] = nums[i - 1] * leftProducts[i - 1]
    }

    rightProducts := make([]int, size)
    rightProducts[size - 1] = 1
    for i := size - 2; i >= 0; i-- {
        rightProducts[i] = nums[i + 1] * rightProducts[i + 1]
    }

    answer := make([]int, size)
    for i := 0; i < size; i++ {
        answer[i] = leftProducts[i] * rightProducts[i]
    }

    return answer
}

其它语言

欢迎贡献代码到 LeetCode.blog GitHub -> 238. 除自身以外数组的乘积。感谢！

题解2的思路：滚动变量 O(1)

空间优化：利用输出数组存储中间结果，避免额外空间
两阶段计算：先计算左侧乘积存入结果，再动态计算右侧乘积并直接合并
原地操作：仅使用一个变量动态维护右侧乘积

步骤

初始化结果数组：
- 创建大小相同的answer数组，初始值全1
计算左侧乘积（左→右遍历）：
- 初始化left_product = 1
- 遍历时：answer[i] = left_product，然后left_product *= nums[i]
计算右侧乘积并合并（右→左遍历）：
- 初始化right_product = 1
- 遍历时：answer[i] *= right_product，然后right_product *= nums[i]
返回结果数组
- 空间复杂度：O(1)（输出数组不计入空间复杂度）

复杂度

时间复杂度

O(N)

空间复杂度

O(1)

Ruby #

# @param {Integer[]} nums
# @return {Integer[]}
def product_except_self(nums)
  size = nums.size
  answer = Array.new(size, 1)

  left_product = 1
  (0...size).each do |i|
    answer[i] = left_product
    left_product *= nums[i]
  end

  #    nums: [1,  2, 3, 4]
  #  answer: [1,  1, 2, 6]  left_product done 
  #  answer: [24,12, 8, 6] right_product done

  right_product = 1
  (size - 1).downto(0) do |i|
    answer[i] *= right_product
    right_product *= nums[i]
  end

  answer
end

Python #

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        size = len(nums)
        answer = [1] * size

        left_product = 1
        for i in range(size):
            answer[i] = left_product
            left_product *= nums[i]

        #    nums: [1,  2, 3, 4]
        #  answer: [1,  1, 2, 6]  left_product done 
        #  answer: [24,12, 8, 6] right_product done

        right_product = 1
        for i in range(size-1, -1, -1):
            answer[i] *= right_product
            right_product *= nums[i]

        return answer

Java #

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] answer = new int[size];
        Arrays.fill(answer, 1);

        int leftProduct = 1;
        for (int i = 0; i < size; i++) {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }

        //    nums: [1,  2, 3, 4]
        //  answer: [1,  1, 2, 6]  leftProduct done 
        //  answer: [24,12, 8, 6] rightProduct done

        int rightProduct = 1;
        for (int i = size - 1; i >= 0; i--) {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }
}

C++ #

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int size = nums.size();
        vector<int> answer(size, 1);

        int left_product = 1;
        for (int i = 0; i < size; ++i) {
            answer[i] = left_product;
            left_product *= nums[i];
        }

        //    nums: [1,  2, 3, 4]
        //  answer: [1,  1, 2, 6]  left_product done 
        //  answer: [24,12, 8, 6] right_product done

        int right_product = 1;
        for (int i = size - 1; i >= 0; --i) {
            answer[i] *= right_product;
            right_product *= nums[i];
        }

        return answer;
    }
};

JavaScript #

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
  const answer = [];
  let left_product = 1;

  for (let i = 0; i < nums.length; i++) {
    answer[i] = left_product;
    left_product *= nums[i];
  }

  //  nums: [1,  2, 3, 4]
  //  answer: [1,  1, 2, 6]  left_product done 
  //  answer: [24,12, 8, 6] right_product done

  right_product = 1;

  for (let i = nums.length - 1; i >= 0; i--) {
    answer[i] *= right_product;
    right_product *= nums[i];
  }

  return answer;
};

C# #

public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int size = nums.Length;
        int[] answer = new int[size];
        Array.Fill(answer, 1);

        int leftProduct = 1;
        for (int i = 0; i < size; i++)
        {
            answer[i] = leftProduct;
            leftProduct *= nums[i];
        }

        //    nums: [1,  2, 3, 4]
        //  answer: [1,  1, 2, 6]  leftProduct done 
        //  answer: [24,12, 8, 6] rightProduct done

        int rightProduct = 1;
        for (int i = size - 1; i >= 0; i--)
        {
            answer[i] *= rightProduct;
            rightProduct *= nums[i];
        }

        return answer;
    }
}

Go #

func productExceptSelf(nums []int) []int {
    n := len(nums)
    answer := make([]int, n)

    answer[0] = 1
    for i := 1; i < n; i++ {
        answer[i] = answer[i-1] * nums[i-1]
    }

    right := 1
    for i := n - 1; i >= 0; i-- {
        answer[i] *= right
        right *= nums[i]
    }

    return answer
}

其它语言

欢迎贡献代码到 LeetCode.blog GitHub -> 238. 除自身以外数组的乘积。感谢！

上一题下一题

游客

全部题解

Welcome !

LeetCode Python, Java, C++ > 数组 > 238. 除自身以外数组的乘积 > 已支持 Ruby, Python, Java, C++, JavaScript, C#, Go > GitHub 或 转发

示例 1:

示例 2:

约束:

思路 上一题下一题

“预计算技术”的模式

主要应用场景

步骤

复杂度

时间复杂度

空间复杂度

Ruby #

Python #

Java #

C++ #

JavaScript #

C# #

Go #

其它语言

题解2的思路：滚动变量 O(1)

步骤

复杂度

时间复杂度

空间复杂度

Ruby #

Python #

Java #

C++ #

JavaScript #

C# #

Go #

其它语言

LeetCode Python, Java, C++ > 数组 > 238. 除自身以外数组的乘积 > 已支持 Ruby, Python, Java, C++, JavaScript, C#, Go > GitHub 或转发

思路
上一题下一题