Problem: 238. 除自身以外数组的乘积

思路

前后缀积

⏰ 时间复杂度: $O(n)$
🌎 空间复杂度: $O(n)$

class Solution {
	public int[] productExceptSelf(int[] nums)
	{
		int n = nums.length;
		int[] p = new int[n];//除去本身的前缀乘积
		int[] q = new int[n];//除去本身的后缀乘积
		p[0] = 1;
		for (int i = 1; i < n; i++)
			p[i] = nums[i - 1] * p[i - 1];
		q[n - 1] = 1;
		for (int i = n - 2; i >= 0; i--)
			q[i] = nums[i + 1] * q[i + 1];
		int[] ans = new int[n];
		for (int i = 0; i < n; i++)
			ans[i] = p[i] * q[i];
		return ans;
	}
}