[LeetCode]Product of Array Except Self

最简单的方法是求出所有数的积，然后对于每个数，直接用积除以它，就是我们要的答案。但是题目不允许这样做，我们可以观察到处在index i的数的答案取决于其两边的数，所以我们可以用dp的方法，从左到右一遍统计左边的积，从右到左统计一遍右边的积即可。时间复杂度O(n)，代码如下：

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

view raw Product of Array Except Self.cpp hosted with ❤ by GitHub