[leetcode]3321. Find X-Sum of All K-Long Subarrays II

※：這題是leetcode週賽419th的題目

說明省略，請參考之3318的說明

題目：3321. Find X-Sum of All K-Long Subarrays II
關鍵字：演算法

看到似曾相識的題目，不過難度卻從easy變為hard，就可以想像到一定是有更麻煩的輸入或更嚴格的條件了，結果也確實如此，直接複製3318使用的解法會超出時間。

由於上次練習3318時已經把自己的解法優化到沒有想法了，這題顯然是需要從根本切入，使用更好的演算法，因此這次就從前面完成的大神如何解題來學習吧！

第一版，改自他人的寫法

分析完時間複雜度之後，發現演算法易開始讀取輸入資料加入物件的次數和我在3318的一樣，先用一個迴圈把nums所有內容加入儲存的結構，如下圖，左邊是我的右邊是評論區改編的寫法。
也就是說，差異在儲存和計算的方式上。

我的邏輯在一開始先把前k個數字加入，並以這組計算完輸出的第一個答案再開始下個迴圈，依序加入下一個數字再移除最早的數字，然後再計算。

他的做法最大的差異在於自己建了一個物件，裡面的組成有出現次數和數值兩欄位，並定義好compareTo函式，讓這個物件可以加入TreeSet結構之中，並根據次數與數值得到先後順序，能方便的取得其中目前最大最小的物件，與我要從整個map取得次數最多的次數是多少，再取得有哪些數字出現這樣的次數，最後取得最大的數字，這樣的過程造成了效能上的差異。

更新次數的時候不像我取得原本的次數之外還要移除記錄在不同次數下的數字移動到另一個次數下，而是以<數字, 次數>為單位，更新全部直接移除原本的紀錄，再新增一個物件加入(次數+1或-1)。

除此之外，在每次計算k個數字的答案時都會做一個平衡的動作，在兩個結構，分別記錄目前較大的數字(large)與次數和目前較小的數字與次數(small)，比較large的最小值和small的最大值是否應交換，並且更新紀錄large所有次數*數值的總值(sum)。
例如原本small的<3, 2>小於large的<4, 2>，但是多一個3就會變成<3, 3>大於<4, 2>。

更詳細的說明可以看程式註解。

後續

這題以現在的我來說，能做的最多就是按照自己的習慣與喜好調整程式的結構，沒辦法對演算法做什麼修正。

最大的收穫大概就是使用TreeMap加TreeSet的天然排序規則時還是會因為讀取的次數造成較差的效能，並且應該善用TreeSet的排序特性自定義排序規則用反覆的新增和刪除操作完成功能。

那麼，如果把這樣的寫法回頭用在3318上會得到什麼樣的效能呢？

意外的，效能和原本的寫法一致，維持原本的11ms，看來主要差異還是在於輸入的參數數值數量與差異過大，導致我的做法不適用。