题目描述
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
2 <= nums.length <= 10^5-30 <= nums[i] <= 30The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
题目分析
题目要求在O(n)时间复杂度内用O(1)的额外空间来求解，假设最终的结果数组为ans，我们不妨看以下2个元素: ans[i], ans[i+1]
对于 ans[i]而言，它等于 prefix[:i] * suffix[i+1:]
prefix[:i]表示从从nums[0]直到nums[i-1]元素的乘积
suffix[i+1:]表示从nums[i+1]直到最后一个元素的乘积
对于ans[i+1]，它等于 prefix[:i+1] * suffix[i+2:]
那么，我们不妨定义2个元素，prefixProd 与 suffixProd； prefixProd定义为前i个元素的乘积，suffixProd定义为后i个元素的乘积
接着我们遍历整个数组，将i与len(nums)-1-i看做头尾2个指针，一个计算prefixProd, 一个计算suffixProd；
头指针同时负责数组元素i的前缀乘积，尾指针负责数组元素的后缀乘积
这样，我们便可以在O(n)的时间复杂度内，对所有元素完成前缀乘积与后缀乘积的相乘计算，得到最终结果
示例代码
func productExceptSelf(nums []int) []int {
// 前缀乘积
prefixProd := 1
// 后缀乘积
suffixProd := 1
len := len(nums)
// 结果数组
res := make([]int, len)
//全部初始化为1
for i := 0; i < len; i++ {
res[i] = 1
}
// 遍历原数组
for i := 1; i < len; i++ {
// 计算前缀乘积
prefixProd *= nums[i-1]
// 头指针元素乘上 前缀乘积
res[i] *= prefixProd
// 计算后缀乘积
suffixProd *= nums[len-i]
// 尾指针元素乘上 后缀乘积
res[len-1-i] *= suffixProd
}
return res
}