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

思考：

除自身之外，所有元素的乘积，一开始想到的是保存两个数组left和right，分别保存左侧/右侧元素的乘积，然后求某一位，只用求left[i+1] * right[i-1]乘积即可。后来发现对空间的利用率太低了，没必要所有都保存到两个数组之中；而且在边界条件的时候还要专门写出来判断。

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

修改之后：

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		int n = nums.size();
        vector<int> res(n,1);
        res[0] = 1;
        //计算某位左侧元素的乘积
        for(int i =1 ;i <n;i++){
            res[i] = res[i-1] * nums[i-1];
        }
        int right =1;//右侧的乘积
        for(int i = n-1;i >= 0;i--){
            res[i] *= right;
            right *= nums[i];
        }
		return res;
	}
};