leetcode238-除自身以外数组的乘积

leetcode 238

思路

可以在不使用除法的情况下，利用前缀积和后缀积来实现解答

• 前缀积：对每个位置，计算当前数字左侧的所有数字的乘积
• 后缀积：对每个位置，计算当前数字右侧的所有数字的乘积
  结合这两种思想，可以在一次遍历中完成计算
  步骤：
• 第一次遍历，计算每个位置左侧的前缀积，并直接保存在 answer 中
• 第二次遍历，从右往左计算右侧的后缀积，并与 answer 中存储的前缀积相乘，得到最终结果

前缀积部分：
使用一个变量 prefix 初始化为 1，遍历数组 nums，对于每个位置 i，将 prefix 保存到 answer[i] 中，并更新 prefix 为 prefix * nums[i]。这样，answer[i] 存储的是 nums 数组中所有 i 左边元素的乘积
后缀积部分：
使用一个变量 suffix 初始化为 1，从数组的右侧开始遍历。对于每个位置 i，将 suffix 与 answer[i] 相乘，更新 suffix 为 suffix * nums[i]。这样，answer[i] 最终保存的是 i 左右两边元素的乘积

时间复杂度：O(n) 空间复杂度：O(1)

假设nums = [1,2,3,4]
前缀积得到的nums = [1,1,2,6] 每个元素左侧的乘积
后缀积得到的nums = [24,12,8,6]

实现

var productExceptSelf = function (nums) {let len = nums.length;const answer = new Array(len).fill(1)let prefix = 1;// 计算前缀积for (let i = 0; i < nums.length; i++) {answer[i] = prefix;prefix *= nums[i]}let suffix = 1;// 计算后缀积for (let i = len - 1; i >= 0; i--) {answer[i] = answer[i] * suffix;suffix *= nums[i]}return answer;
};