0238_product-of-array-except-self

README

0238_product-of-array-except-self

题目有个限制, 即使是所有元素的product也会是int32类型能够表示的.

题目要求:

• 时间复杂度:O(n)
• 不使用除法

设:

• f(i), 0 <= i < n, 为解output[i].
• g(i) = nums[0] * nums[1] ... * nums[i-1]
  • g(0) = 1
• h(i) = nums[i+1] * nums[i+2] ... * nums[n - 1]
  • h(n-1) = 1

有f(i) = g(i) * h(i)

我们可以通过两次遍历求得g和h的array, 达成了题目要求

题目进一步对于空间作出限制, 不过用来返回答案的数组空间不计入, 所以我们可以保存第一次遍历g的结果, 在第二次遍历时直接计算并覆盖g为解的数组f, 最后返回解f.