题目
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
题意
给定具有n个整型的数组，对应输出一个数组，该数组元素为除去原数组下标位置元素的其他元素的乘积。
要求，时间复杂度为O(N),不用除法，不使用额外的存储空间。
例子
Example:
Input: [1,2,3,4] Output: [24,12,8,6]
题解
对于输出数组out，每个元素等于
num[0]*...num[i-1]*num[i+1]*...num[n-1]
所以可以先遍历一遍，将每个元素左边的乘积先保存在out中，然后在从后遍历，累加后半部分的乘积与前半部分成绩相乘。
代码
func productExceptSelf(nums []int) []int {
Len := len(nums)
out := make([]int,Len)
//累乘前半部分
for i:=0;i<Len;i++{
if i==0{
out[i]=1
continue
}
out[i] = out[i-1]*nums[i-1]
}
//累乘后半部分
sum := 1
for i:=Len-2;i>=0;i--{
sum *= nums[i+1]
out[i]=out[i]*sum
}
return out
}
总结
因为之前有做过类似思路的题目，所以想了一会就反应过来可以这么去做，也是一遍过了，没什么特别的地方。硬要有这里面也有一点分治的思路，先算一半，在算另外一半。
