本題資訊
難度：medium
使用語言：C++
相關概念：Arrays
題目敘述
Write a function that takes in a non-empty array of integers and returns an array of the same length, where each element in the output array is equal to the product of every other number in the input array.
In other words, the value at output[i] is equal to the product of every number in the input array other than input[i]. Note that you’re expected to solve this problem without using division.
Input:array = [5, 1, 4, 2]
Output:[8, 40, 10, 20]
總而言之就是依照順序，除了目前位置的數字外其他相乘。
Idea
題目特別強調不要用除法XD 若目前走到的位置是 i，最簡單的想法是巡覽整個陣列，把不等於 i 的位置相乘，但因為每個位置都必須這樣做，所以內外都要有迴圈，理所當然時間上會不好看。
由於這題性質是陣列處理，陣列上還蠻常有從頭從尾處理以降低複雜度的做法。這題是除了當前元素的累乘，應該是可以，但實際上要如何操作呢？
假設我們現在有個陣列長相如下：
我們所要求的結果可以看做是這樣：
黑色部分是第一輪我們要相乘的內容，紅色部分是第二輪我們要再相乘上去的結果。也就是說第一輪累積相乘的結果先存在 result 內，再以同樣的方式倒序走回來相乘。
#include <vector>
using namespace std;
vector<int> arrayOfProducts(vector<int> array) {
vector<int> result;
result.push_back(1);
int temp = array[array.size()-1];
for (int i = 1; i < array.size(); i++){
result.push_back(array[i-1] * result[i-1]);
}
for (int i = array.size() - 2; i >= 0; i--){
result[i] = temp * result[i];
temp = temp * array[i];
}
return result;
}
時間複雜度：\(O(n)\)，\(n\) 是 array 長度
空間複雜度：\(O(n)\)
