主題
題目連結：
題目意譯：
你被給定兩個非負整數陣列 rowSum 和 colSum，其中 rowSum[i] 為一個二維矩陣中第 i 列的元素總和，而 colSum[j] 為一個二維矩陣中第 j 行的元素總和。換句話說，你不知道矩陣中的元素，但是你知道每一行、列的元素總和。
請找出任意一個非負整數矩陣，其大小為 rowSum.length × colSum.length，並滿足 rowSum 和 colSum 的條件。
回傳一個二維陣列代表著滿足條件的矩陣。保證至少存在一個矩陣滿足條件。
限制：
1 ≦ rowSum.length, colSum.length ≦ 500
0 ≦ rowSum[i], colSum[i] ≦ 10 ^ 8
sum(rowSum) == sum(colSum)
範例測資：
範例 1：
輸入： rowSum = [3,8], colSum = [4,7]
輸出： [[3,0], [1,7]]
解釋：
第 0 列： 3 + 0 = 3 == rowSum[0]
第 1 列： 1 + 7 = 8 == rowSum[1]
第 0 行： 3 + 1 = 4 == colSum[0]
第 1 行： 0 + 7 = 7 == colSum[1]
行列各自的總和都有對到，並且所有元素都是非負整數。
另一個可能的矩陣為 [[1,2], [3,5]]
範例 2：
輸入： rowSum = [5,7,10], colSum = [8,6,8]
輸出： [[0,5,0], [6,1,0], [2,0,8]]
解題思維：
按照以下策略為矩陣（假設所求矩陣名為 A）填入數字即可：
如果現在位於第 i 列第 j 行，則將 A[i][j] 設為 min(rowSum[i], colSum[j])；
並將 rowSum[i] 和 colSum[j] 各自減去 A[i][j]。
所有格子填完之後的矩陣 A 即符合條件。
問題來了，為什麼上面這個策略行得通？
首先我們可以看到每行或每列最後填的格子才「有機會」出事。例如說如果你選擇從左至右由上至下填數字的話（以下的填入順序都預設如此），真的會出事的格子只會是位於第 r - 1 列或第 c - 1 行的格子，其中 r = rowSum.length 、 c = colSum.length。
因為我們在每一格時會選較小的數字填，所以必定會解決列或是行其中一者的條件。而沒有被解決的條件會「留到之後」解決。所以真正的問題是為何填入每一列或每一行最後一格時不會出事。
那什麼是「出事」？例如說現在填的是第 x 列的最後一格，則所謂的「出事」即為此時的 rowSum[x] > colSum[c - 1]，因為此時會選擇填入 colSum[c - 1] 而 rowSum[x] 將無法被滿足。
我們可以用反證法證明不可能出事——假設真的出事了，承上例，此時 rowSum[x] > colSum[c - 1]。
首先可以看到先前一定有填入其他數字，即 c > 1。因為如果 c == 1，則根據題目保證答案存在的條件，此時 colSum[0] 必將是 rowSum[0] + rowSum[1] + …… + rowSum[r - 1] 之總和，因此不可能觸發出事的條件。
假設先前第 x 列填入的數字為 a0 、 a1 、 …… 、 ak，其中 k == c - 2。並且我們可以看到 a0 、 a1 、 …… 、 ak 會是其他行的總和條件（不然 rowSum[x] 早就被滿足了）。
因此我們可以看到最原本 rowSum[x] 之值會是 C + a0 + a1 + …… + ak，其中 C 代表著現在 rowSum[x] 之值。並且矩陣中所有元素之和應為 a0 + a1 + …… + ak + colSum[c - 1]。
此時我們根據原先假定的條件得到
C + a0 + a1 + …… + ak > a0 + a1 + …… + ak + colSum[c - 1]
也就是說
「一開始 rowSum[x] 之值」 > 「矩陣所有元素總和」
而這是不可能的事情。因此 rowSum[x] > colSum[c - 1] 之情況是不可能發生的。
由於上面討論的是「列」的情況，「行」的情況也要討論。但是可以看到這部份是與上同理的。
證畢。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
