[leetcode]3318. Find X-Sum of All K-Long Subarrays I

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

如題目範例，第一組測資

輸入：nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

每6個為一組得到
[1,1,2,2,3,4]、[1,2,2,3,4,2]、[2,2,3,4,2,3]

出現次數多寡分別為(列出的順序即為前面說明的排序規則)
{1:2, 2:2, 3:1, 4:1}、{2:3, 4:1, 3:1, 1:1}、{2:3, 3:2, 4:1}

取得出現次數前2多的數字之總值相加
1x2+2x2、2x3+4x1、2x3+3x2 => [6, 10, 12]

[6, 10, 12]就是答案

題目：3318. Find X-Sum of All K-Long Subarrays I
關鍵字：演算法、有序集合(SortedSet)、有序映射表(SortedMap)

這題的重點是如何有效率的解決問題，理解題目之後可以非常直覺的依照題目要求寫出如下的程式（細節省略）。

public int[] findXSum(int[] nums, int k, int x) {
    int[] answer = new int[nums.length - k + 1];
    for(int index = 0; index < nums.length - k; index++) {
        int[] subArray = getSubArray(nums, index, k);
        // 計數、排序、加總
        answer[index] = ??? // 加總結果
    }
    return answer;
}

private int[] getSubArray(int[] nums, int fromIndex, int length) {
    // 取得目標子陣列
    // ...
}

這樣的寫法對我來說並不理想，所以並沒有嘗試能否通過leetcode的測試。不理想的原因是有多餘的計算，先統計1st~6th再統計2nd~7th的過程中，2nd~6th就被重複讀取了，具體的統計次數會是「(n - k + 1)*k」次。

我所期望的是只讀取nums每個數字一次，總共n次就得到最後答案的做法。

符合期望的理想解法

建立了一個類別XSumData，提供加入和移除數字的方法，並在這過程中更新該數字目前累積出現的次數。

記錄次數的動作為了讀取的效率分成兩個物件，nowCountMap記錄每個數字目前出現的次數，dataMap記錄每個次數目前有哪些數字符合，並且使用有序的Map和Set，讓出現次數和數字都由大到小排列。

使用add加入新的數字時更新nowCountMap把新數字的出現次數+1，並取得這個計算後的值。
如果是1就表示原本沒有記錄，只要把這個數字增加到次數1的分組就行；2以上則要移出原本的組別加入新的分組，例如出現第3次時就不是出現2次的數字，而要加入3次的分組了。

使用remove將要排除的數字次數-1，也把所屬的分組-1。把要加入的要移除的都處理完之後再呼叫getSum取得符合的計算結果。

回到題目，題目要記錄的是每k個一組的結果，首先add前k個數字的次數，getSum取得1~k的答案，再把第1個數字remove並add第k+1個數字，再次使用getSum得到2~k+1的答案......直到結束，這過程中反覆透過getSum蒐集的數值列表就是答案。

這個做法的好處是nums的每個數字都只有取得1~2次，也不用重複計算和排序，而且很容易讀&說明。

對於效率這次已經滿足，所以就不繼續研究其他寫法了。