238. 除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例：
输入: [1,2,3,4]
输出: [24,12,8,6]
说明：
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
分析：
题目明确要求不允许使用除法。如果可以使用除法，只需要计算出数组的总乘积，接着除去每个位置上的元素就可以了。不允许使用除法，意味着求整个数组的乘积是没有意义的。对每个元素，我们必须求出除它自身以外数组的乘积，我们可以将这个乘积划为两部分，左子数组乘积以及右子数组乘积。
进一步我们以数组形式保存这个乘积。这样对每一个元素，我们不需要重新遍历数组来计算乘积，只需要对乘积数组的前一位乘以当前元素值就可以了。
再进一步，题目提示我们可以做到常数时间复杂度，按照题目的意思，就是只有一个额外的输出数组。仔细想想 由于我们遍历的数组是连续的，并且是完整的，因此我们并不需要类似于动态规划的备忘法以数组来存储元素，只需要两个变量left， right就可以顺序遍历并保存左右子数组的乘积。不过由于我们需要返回一个输出数组，因此我们仍然需要一个数组，另外的一个值就可以用一个变量替代了。
代码（Golang）：
法1（保存两个数组）：
func productExceptSelf(nums []int) []int {
var (
ans = make([]int, len(nums))
left = make([]int, len(nums))
right = make([]int, len(nums))
)
left[0] = 1
right[len(nums) - 1] = 1
for i := 1; i < len(nums); i++ {
left[i] = left[i - 1] * nums[i - 1]
}
for i := len(nums) - 2; i > -1; i-- {
right[i] = right[i + 1] * nums[i + 1]
}
for i := 0; i < len(nums); i++ {
ans[i] = left[i] * right[i]
}
return ans
}
法2（变量+数组）：
func productExceptSelf(nums []int) []int {
ans := make([]int, len(nums))
ans[0] = 1
right := 1
for i := 1; i < len(nums); i++ {
ans[i] = ans[i - 1] * nums[i - 1]
}
for i := len(nums) - 2; i > -1; i-- {
right *= nums[i + 1]
ans[i] *= right
}
return ans
}
总结：
当遇到这种需要保存状态的情况时，很多时候都可以压缩状态。搞清楚我们需要的是什么，就可以写出更清晰的代码。