Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].
Solve itwithout divisionand in O(n).
For example, given[1,2,3,4], return[24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output arraydoes notcount as extra space for the purpose of space complexity analysis.)
如果能够使用除法这道题就没有什么好说的了，问题是不能使用除法。这道题的解法很巧妙。
对于一个数组[1,2,3,4]，，可以对它进行两次遍历。第一次从左到右遍历，第二次从右到左遍历。第一次遍历时记录它左边所有数的乘积，第二次遍历时将它右边的数乘上这个乘积就是这个数组中除了自身这个数以外所有数的乘积了。如下：
runtime:60ms
class Solution {public:vector<int> productExceptSelf(vector<int>& nums) {int length=nums.size();vector<int> result(length,1);for(int i=1;i<length;i++){result[i]=result[i-1]*nums[i-1];}int tmp=1;for(int i=length-1;i>=0;i–){result[i]=result[i]*tmp;tmp*=nums[i];}return result;}};
版权声明：本文为博主原创文章，未经博主允许不得转载。
背着背包的路上，看过许多人，听过许多故事，
