# 238. Product of Array Except Self

Given an array nums of  n  integers where  n  > 1,  return an array output such that output[i] is equal to the product of all the elements of numsexcept nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Note: Please solve it without division and in O( n ).

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

C++ 解法一：

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> fwd(n, 1), bwd(n, 1), res(n);
for (int i = 0; i < n - 1; ++i) {
fwd[i + 1] = fwd[i] * nums[i];
}
for (int i = n - 1; i > 0; --i) {
bwd[i - 1] = bwd[i] * nums[i];
}
for (int i = 0; i < n; ++i) {
res[i] = fwd[i] * bwd[i];
}
return res;
}
};

Java 解法一：

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

C++ 解法二：

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
res[i] = res[i - 1] * nums[i - 1];
}
int right = 1;
for (int i = nums.size() - 1; i >= 0; --i) {
res[i] *= right;
right *= nums[i];
}
return res;
}
};

Java 解法二：

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

Github 同步地址：

https://github.com/grandyang/leetcode/issues/238

Trapping Rain Water

Maximum Product Subarray

https://leetcode.com/problems/product-of-array-except-self/

https://leetcode.com/problems/product-of-array-except-self/discuss/65638/My-simple-Java-solution

https://leetcode.com/problems/product-of-array-except-self/discuss/65622/Simple-Java-solution-in-O(n)-without-extra-space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation