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
}
}