Leetcode 238 - Product of Array Except Self（递推）

题意

给定一个数组a[]，对于其中的每一个元素x，求数组中所有数相乘并除以该元素x的结果。并且不能使用除法。

思路

算法1

O(n)$O(n)$时间和O(n)$O(n)$空间。

我们维护一个l[i]和r[i]数组，分别代表从左往右乘到元素ai$a_i$的积和从右往左乘到元素ai$a_i$的积。

那么，对于我们要求的结果ansi=li−1⋅ri+1$ans_i = l_{i - 1} · r_{i + 1}$。

算法2

O(n)$O(n)$时间和O(1)$O(1)$空间。

我们需要想办法去优化一下空间，其实从我们上面的式子ansi=li−1⋅ri+1$ans_i = l_{i - 1} /cdot r_{i+1}$就可以发现：我们的li$l_i$是可以从左向右递推得到的，我们的ri$r_i$也可以从右向左递推得到，并且在递推过程中，我们的l和r其实不用用数组保存。

那么我们只需要从左往右遍历一遍得到ansi=li−1$ans_i = l_{i-1}$，然后再从右往左遍历一遍得到ansi=ansi∗ri+1$ans_i = ans_i * r_{i + 1}$即可。

代码