[面試]找到一個元素，可以將數組分成兩個乘積相等的子數組

來自專欄快樂編程

題目：

給定一個大小為N的數組。查找一個元素，可以將數組分成兩個等積的子數組。 如果沒有這樣的元素，則列印-1。

比如:

輸入 : 1 4 2 1 4輸出 : 2以2為分割元素, 子數組 : {1, 4} 以及 {1, 4}1*4 = 1*4輸入 : 2, 3, 4, 1, 4, 6輸出 : 1以1為分割元素, 子數組 : {2, 3, 4} 以及 {4, 6}2*3*4 = 4*6

分析：

一個簡單的思路是從第二個元素開始的進行遍歷。 計算左側元素和右側元素的乘積。 如果這兩個產品相同，則返回元素。

時間複雜度：O（N^2）

解題：

更好的解決方案是使用前綴和後綴數組。 用left[i]表示 a[0]a[1]...a[i-1]的乘積，right[i]同理表示a[i+1]a[i+2]...a[N-1]的乘積。

遍歷一次數組可以建立 left[0..N-1]，再遍歷一次建立right[0 ... N-1]

再需要一次遍歷找出 left[i] == right[i]

時間複雜度：O(N)

輔助空間：O(N)

代碼：

略

輔助空間可以優化到O(1) 留給讀者思考。