主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始數且由 3 × n 個元素所組成的整數陣列 nums。
你被允許從 nums 中移除任意一個大小為 n 的子序列。而剩餘 2 × n 個元素將會被分成兩個大小相同的部份：
前 n 個元素屬於第一個部份，而它們的總和值為 sumfirst。
後 n 個元素屬於第二個部份，而它們的總和值為 sumsecond。
兩部份的總和差值定義為 sumfirst - sumsecond。
例如說，如果 sumfirst = 3 且 sumsecond = 2，則差值為 1。
同樣地，如果 sumfirst = 2 且 sumsecond = 3，則差值為 -1。
回傳移除 n 個元素後可以得到之兩部份的總和差值最小值。
限制：
nums.length == 3 × n
1 ≦ n ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： nums = [3,1,2]
輸出： -1
解釋： 此例中，nums 有 3 個元素，因此 n = 1。
所以我們必須移除 1 個元素並將剩餘陣列分成兩個大小相同的部份。
- 如果我們移除 nums[0] = 3，該陣列會變為 [1,2]。兩部份的總和差值為 1 - 2 = -1。
- 如果我們移除 nums[1] = 1，該陣列會變為 [3,2]。兩部份的總和差值為 3 - 2 = 1。
- 如果我們移除 nums[2] = 2，該陣列會變為 [3,1]。兩部份的總和差值為 3 - 1 = 2。
兩部份的總和差值最小值為 min(-1,1,2) = -1。
範例 2：
輸入： nums = [7,9,5,8,1,3]
輸出： 1
解釋： 此例中 n = 2。所以我們必須移除 2 個元素並將剩餘陣列分成兩個部份各自有著兩個元素。
如果我們移除 nums[2] = 5 和 nums[3] = 8，該陣列會變為 [7,9,1,3]。兩部份的總和差值為 (7+9) - (1+3) = 12。
為了得到最小差值，我們應移除 nums[1] = 9 和 nums[4] = 1。該陣列會變為 [7,5,8,3]。兩部份的總和差值為 (7+5) - (8+3) = 1。
可以證明不可能得到小於 1 的差值。
解題思維：
如果我們只看「第一部份」，則其最遠可以包到的元素為 nums[2n - 1]，因為第二部份最少要 n 個數字。相似地，第二部份最遠可以包到 nums[n] 這個元素。
而從以上這點我們可以將題目敘述改寫成：
選定一個元素 nums[i]，使得 nums[0] ~ nums[i] 屬於第一部份、nums[i + 1] ~ nums[3n - 1] 屬於第二部份。其中 n - 1 ≦ i < 2n。
接著從各個部份中移除若干個元素直到大小恰好為 n 個數字為止。因此第一部份會移除 i - n + 1 個數字，而第二部份則是移除 2n - i - 1 個數字。
而可以看到為了將差值最小化，我們需要讓 sumfirst 越小越好並讓 sumsecond 越大越好。因此第一部份移除的數字會是最大的那幾個；同理，第二部份移除的數字會是最小的那幾個。
不過如果我們現在直接窮舉 i 值來一一檢查的話，會超時。因為 i 值有 n + 1 個數值而要從每一個部份移除最小或最大者需要 O(n × log(n)) 的時間。因此這邊的時間複雜度會是 O((n ^ 2 × log(n))。
但是如果我們仔細看當 i 逐漸遞增的時候，實際上 i = k 和 i = k + 1 兩個狀況下，在 i = k 時中第一部份移除的數字在 i = k + 1 時也會被移除。
因此我們可以利用這個「繼承」的特性來減少重複移除數字的次數。也就是說每當 i 加一之後，將 nums[i] 加到第一部份中並移除現在剩餘所有數字中最大者。
這樣子由小到大先掃過一輪的 i 值便可以得到所有 i 值下對應的第一部份 sumfirst 最小值。
同理，從大到小掃過一輪 i 值便可以得到所有 i 值下對應的第二部份 sumsecond 最大值。
最後再掃過一次所有 i 值，根據上面先行計算的第一部份和第二部份各自的最小和最大總和並相減。其中的最小值即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
