238. Product of Array Except Self

這道題應該蠻重要的, 我沒有注意到

一開始我還真的沒有頭緒, 看相似題說跟Trapping Rain Water一樣

我還是想不透

原來是我們可以去找出當前index左右兩邊的乘積, 最後再把兩邊乘起來就行了, 跟裝水我們會去找兩邊的最高值是一樣的

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> right_mul(nums.size(), 1);
        vector<int> left_mul(nums.size(), 1);
for(int i = 0; i < nums.size() -1 ;i++){
            right_mul[i + 1] = right_mul[i] * nums[i];
       
        }
  
        for(int i = nums.size() -1;i>0;i--){
            left_mul[i-1] = left_mul[i] * nums[i];
           
        }
        for(int i = 0;i< nums.size();i++){
            nums[i] = right_mul[i] * left_mul[i];
        }
        return nums;
    }
};

follow up 問能不能用o(1)的空間

class Solution {
  public:
    vector<int> productExceptSelf(vector<int> &nums) {
        vector<int> res(nums.size(), 1);
        int left = 1;
        for (int i = 1; i < nums.size(); i++) {
            left *= nums[i - 1];
            res[i] = left;
        }
        int right = 1;
        for (int i = nums.size() - 2; i >= 0; i--) {
            right *= nums[i + 1];
            res[i] *= right;
        }
        return res;
    }
};

就是用left, right一路記下來