LeetCode 面试经典150题 238.除自身以外数组的乘积

本文主要是介绍LeetCode 面试经典150题 238.除自身以外数组的乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

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

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

思路：利用前缀和的思想，将前缀和后缀分开算，建立ans数组，先从前往后遍历nums，计算每个nums[i]前缀乘值部分，再从后往前遍历nums，计算每个nums[i]后缀乘值的部分，两部分相乘即是最终的ans[i]。

代码：

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] ans = new int[n];for (int i = 1, j = 1; i <= n; i++) {ans[i - 1] = j;j = j * nums[i - 1];}for (int i = n, j = 1; i >= 1; i--) {ans[i - 1] *= j;j *= nums[i - 1];}return ans;}
}

性能：时间复杂度O（n）    空间复杂度O（1）

这篇关于LeetCode 面试经典150题 238.除自身以外数组的乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---