/**
Given an integer array nums, return an array answer such that answer[i] is
equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit
integer.
You must write an algorithm that runs in O(n) time and without using the
division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit
integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The
output array does not count as extra space for space complexity analysis.)
Related Topics数组 | 前缀和
👍 1269, 👎 0
*/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] lProduct = new int [nums.length];
int[] rProduct = new int [nums.length];
lProduct[0] = 1;
rProduct[nums.length - 1] = 1;
for (int i = 1; i < nums.length; i++) {
lProduct[i] = lProduct[i - 1] * nums[i - 1];
rProduct[nums.length - 1 - i] = rProduct[nums.length - i] * nums[nums.length - i];
}
int[] result = new int [nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = lProduct[i] * rProduct[i];
}
return result;
}
}
//leetcode submit region end(Prohibit modification and deletion)
