主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始的有著 n 個整數之陣列 nums，以及一整數 k。
對於一個 nums 的子陣列，其中心為一索引值 i 並有著半徑 k。它的 k-半徑平均（k-radius average）為 nums 中索引值介於 i - k 到 i + k（含端點）之間的元素之平均。如果索引值 i 之前或是之後少於 k 個元素的話，則其 k-半徑平均之值為 -1。
建立並回傳一長度 n 的陣列 avgs，其中 avgs[i] 為以索引值 i 為中心的子陣列的 k-半徑平均。
x 個元素的「平均」為這個 x 個元素之總和除以 x，其中除法使用的是整數除法。整數除法將會自動地向 0 捨去小數部分。
例如，四個元素 2 、 3 、 1 和 5 的平均為 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，而此數將捨去變為 2。
限制：
n == nums.length
1 ≦ n ≦ 10 ^ 5
0 ≦ nums[i], k ≦ 10 ^ 5
範例測資：
範例 1：
輸入： nums = [7,4,3,9,1,8,5,2,6], k = 3
輸出： [-1,-1,-1,5,4,4,-1,-1,-1]
解釋：
- avg[0] 、 avg[1] 和 avg[2] 為 -1 因為對於每個索引值都少於 k 個元素。
（譯者注：原文即是使用「avg」，儘管題目敘述的定義為「avgs」。根據上下文，這兩個指的是同一個東西）
- 以索引值 3 為中心、半徑 3 的子陣列之總和為 7 + 4 + 3 + 9 + 1 + 8 + 5 = 37。
使用整數除法，avg[3] = 37 / 7 = 5。
- 對於以索引值 4 為中心的子陣列，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4。
- 對於以索引值 5 為中心的子陣列，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4。
- avg[6] 、 avg[7] 和 avg[8] 為 -1 因為對於每個索引值都少於 k 個元素。
範例 2：
輸入： nums = [100000], k = 0
輸出： [100000]
解釋：
- 以索引值 0 為中心、半徑 0 的子陣列之總和為：100000。
avg[0] = 100000 / 1 = 100000。
範例 3：
輸入： nums = [8], k = 100000
輸出： [-1]
解釋：
- avg[0] 為 -1，因為索引值 0 之前以及之後皆少於 k 個元素。
解題思維：
可以看到 avgs 最前面 k 個以及最後面 k 個位置的值皆為 -1（因為根據定義，元素的數量都不夠），即
avgs[0] = avgs[1] = …… avgs[k - 1] = avgs[n - 1] = avgs[n - 2] = …… avgs[n - k] = -1
所以當 n < 2k + 1 時，可以推得 avgs 中每個位置的值皆為 -1。
因此接著我們假設 n ≧ 2k + 1，現在要來計算 avgs[k] 、 avgs[k + 1] 、……：
我們可以先展開一下 avgs[k] 需要的項次，也就是
nums[0] ～ nums[k - 1]，作為中心的左邊部分；
nums[k]，作為中心；
nums[k + 1] ～ nums[2k]，作為中心的右邊部分。
再來我們展開 avgs[k + 1] 需要的項次，即
nums[1] ～ nums[k]，作為中心的左邊部分；
nums[k + 1]，作為中心；
nums[k + 2] ～ nums[2k + 1]，作為中心的右邊部分。
可以看到從 avgs[k] 到 avgs[k + 1] 的項次只差在：少去 nums[0]、多了 nums[2k + 1]。
然後根據類似的論述，可以推得我們從 avgs[i] 到 avgs[i + 1] 時（其中 k ≦ i < n - k），其總和將減去 nums[i - k] 並增加 nums[i + k + 1]。
因此我們也就可以利用滑動視窗（Sliding Window，如這題）的精神來求出 avgs 各個位置的值——即先求出 avgs[k] 所需的項次（也就是先將 nums[0] ～ nums[2k] 加總得一數值 T），然後算出 avgs[k] 真正的值（即 T 除以 (2k + 1)）；接著往後移到 avgs[k + 1]，因此根據上面的觀察將 T 減去 nums[0] 並加上 nums[2k + 1]，然後求出 avgs[k + 1] 真正的值……以此類推。
因此除了 avgs[k] 計算時間為 O(k) 以外，其他位置皆為 O(1) 即可求得。因此總體時間複雜度為 O(n)。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
