30-Day LeetCoding Challenge (Day15)

挑戰賽進行到一半，第三週的第一題就開始是 Medium：238. Product of Array Except Self

題目給定一個陣列，對每個 element i 計算除了他之外的其他 element 乘積。可能是因為題目直觀不難，另外加上了需要Ｏ(Ｎ) 以及不能使用除法的限制。

Input:  [1,2,3,4]
Output: [24,12,8,6]

那如果還是要用暴力法呢，結果就 ＴＬＥ 了 xD

vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ans(nums.size(), 1);
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<nums.size(); j++){
                if(i==j) continue;
                else ans[i] *= nums[j];
            }
        }
        return ans;
    }

借用官方說明圖解，可以發現其實就是自己左邊乘上右邊（好像有點像廢話😆

所以我們可以準備兩個陣列，分別存從左邊乘過來/右邊乘過來的結果

這樣每個 element i 就是相對應的左邊*右邊的乘積囉。

vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> ans(nums.size());
    vector<int> l(nums.size(),1);
    vector<int> r(nums.size(),1);
    
    for(int i=1; i<nums.size(); i++){
        l[i] = l[i-1] * nums[i-1];
    }
    
    for(int i=(int)nums.size()-2; i>=0; i--){
        r[i] = r[i+1] * nums[i+1];
    }
    
    for(int i=0; i<nums.size(); i++)
        ans[i] = l[i] * r[i];

    return ans;
}