主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開始且長度為 n 的二元陣列 nums。nums 可以在任意索引值 i （其中 0 ≦ i ≦ n）分割成兩個(gè)陣列（有可能是空的）numsleft 和 numsright：
numsleft 有著 nums 中所有索引值介於 0 到 i - 1 之間（含端點(diǎn)）的所有元素，而 numsright 有著 nums 中所有索引值介於 i 到 n - 1 之間（含端點(diǎn)）的所有元素。
如果 i == 0，則 numsleft 為空且 numsright 有著 nums 所有元素。
如果 i == n，則 numsleft 有著 nums 所有元素且 numsright 為空。
每個(gè)索引值 i 有著一個(gè)分割分?jǐn)?shù)，其值為 numsleft 中的 0 之個(gè)數(shù)與 numsright 中 1 之個(gè)數(shù)的加總。
回傳所有相異索引值使得這些索引值有著最高的分割分?jǐn)?shù)。你可以按任意順序回傳答案。
限制：
n == nums.length
1 ≦ n ≦ 10 ^ 5
nums[i] 只會(huì)是 0 或是 1。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [0,0,1,0]
輸出： [2,4]
解釋： 分割發(fā)生於索引值
- 0： numsleft 為 []。numsright 為 [0,0,1,0]。分?jǐn)?shù)為 0 + 1 = 1。
- 1： numsleft 為 [0]。numsright 為 [0,1,0]。分?jǐn)?shù)為 1 + 1 = 2。
- 2： numsleft 為 [0,0]。numsright 為 [1,0]。分?jǐn)?shù)為 2 + 1 = 3。
- 3： numsleft 為 [0,0,1]。numsright 為 [0]。分?jǐn)?shù)為 2 + 0 = 2。
- 4： numsleft 為 [0,0,1,0]。numsright 為 []。分?jǐn)?shù)為 3 + 0 = 3。
索引值 2 和 4 都有著最高的分割分?jǐn)?shù) 3。
注意到答案 [4,2] 也可以被接受。
範(fàn)例 2：
輸入： nums = [0,0,0]
輸出： [3]
解釋： 分割發(fā)生於索引值
- 0： numsleft 為 []。numsright 為 [0,0,0]。分?jǐn)?shù)為 0 + 0 = 0。
- 1： numsleft 為 [0]。numsright 為 [0,0]。分?jǐn)?shù)為 1 + 0 = 1。
- 2： numsleft 為 [0,0]。numsright 為 [0]。分?jǐn)?shù)為 2 + 0 = 2。
- 3： numsleft 為 [0,0,0]。numsright 為 []。分?jǐn)?shù)為 3 + 0 = 3。
只有索引值 3 有著最高的分割分?jǐn)?shù) 3。
範(fàn)例 3：
輸入： nums = [1,1]
輸出： [0]
解釋： 分割發(fā)生於索引值
- 0： numsleft 為 []。numsright 為 [1,1]。分?jǐn)?shù)為 0 + 2 = 2。
- 1： numsleft 為 [1]。numsright 為 [1]。分?jǐn)?shù)為 0 + 1 = 1。
- 2： numsleft 為 [1,1]。numsright 為 []。分?jǐn)?shù)為 0 + 0 = 0。
只有索引值 0 有著最高的分割分?jǐn)?shù) 2。
解題思維：
由於 nums 中只有 0 和 1，因此如果我們把 nums 中所有數(shù)字加起來就是 nums 中 1 的數(shù)量。而 0 的數(shù)量只需要從 nums 的長度減去 1 的數(shù)量即可求得。
因此我們可以從索引值 i 的其中一邊（例如右邊）的 1 之?dāng)?shù)量推得索引值 i + 1 同一邊的 1 的數(shù)量（跟滑動(dòng)視窗（Sliding Window）的精神類似，如這題）。然後就可以藉由整體 1 的數(shù)量推得另一側(cè)（例如右邊推得左邊）。
因此我們便可以從索引值 0 開始掃過所有索引值並求得它們的分割分?jǐn)?shù)，找出哪些索引值可以獲得最大值即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
