238. Product of Array Except Self
https://leetcode.com/problems/product-of-array-except-self/
题意：
输出阵列要是输入阵列所有左与右元素的乘积 不包含自己
空间复杂度要 O(n) 而且不能用除法
思路：
题目的限制等于禁止用两层 for
但可以用两次 for
所以第一次先建全部为 1 的输出阵列
让他们从左往右乘
会跟滚雪球一样越滚越大
再从右往左乘
但此时输出阵列已经被动过了
所以要一个 temp 来充当中介
Code:
impl Solution {
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
let mut ans = vec![1; nums.len()];
for i in 1..nums.len() {
ans[i] = ans[i - 1] * nums[i - 1];
}
let mut right = 1;
for i in (0..nums.len()).rev() {
ans[i] *= right;
right *= nums[i];
}
ans
}
}