1. 題意

除了自身外的乘積，題目要求不能用除法做。

2. 題解

不用除法做，那就用前后綴分解的方法做。

時間復雜度$O(n)$

• 兩個數組記錄前后綴乘積

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

事實上這個兩個數組空間都可以直接優化掉，下面的空間復雜度為$O(1)$

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> ans(n, 1);int pre = 1;for (int i = 1;i < n; ++i) {pre *= nums[i - 1];ans[i] *= pre;}int suf = 1;for (int i = n - 2; ~i; --i) {suf *= nums[i + 1];ans[i] *= suf;}return ans;}
};```