Product of Array Except Self

解题思路

这道题的关键在于不能使用除法，且时间复杂度为 O(n)，思路如下：

  1. 既然不能使用除法，就意味着只能使用乘法
  2. 最直接的方式是对于每个位置，都遍历一遍 nums，乘以除自身外的值，但这样的时间复杂度就位 O(n2)
  3. 然后思考如何降低时间复杂度，可以想到第 2 点解法中存在元素重复相乘，于是得出正确思路：在一次遍历过程中，已经乘过的元素结果直接保存到结果数组中，具体代码如下：

代码

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