寫在前面

雖然碰到過很多次這種需要大量額外空間的題，但是看到題的第一反應(yīng)總也不會往那個方向考慮。這是一道簡單題，難度確實不大，但是選對使用什么數(shù)據(jù)結(jié)構(gòu)、使用多少個總是不那么容易的，還是需要慢慢培養(yǎng)這種思路誒。

題目

核心思路

直接法/暴力法(超時)

就像最開始說的，因為看到題并沒有想到使用3個map這么多，所以第一次提交使用的直接法，超時也是理所應(yīng)當?shù)?。這道題直接法思路簡單，先實現(xiàn)一個函數(shù)計算指定范圍數(shù)組的度，然后先求出nums的度(degree)，之后遍歷數(shù)組的每一種可能的范圍，如果度與degree相等，所求的最短子數(shù)組長度就是當前遍歷到的長度與先前最短長度的最小值。遍歷數(shù)組的復(fù)雜度為O(n2)，求度又要O(n)的復(fù)雜度，所以總的復(fù)雜度很大，具體的代碼就不給出了。

3個map3次遍歷

其實根據(jù)題目的意思，數(shù)組的度只與頻率最高的數(shù)有關(guān)，所以沒必要求每個子數(shù)組的度，只要找到頻率最高的數(shù)第一次出現(xiàn)和最后一次出現(xiàn)的位置即可，由于頻率最高的數(shù)可能不止一個，所以再遍歷一次求出最小值即可。所以使用3個map，鍵為數(shù)組元素的值，第一個map的值存儲該元素出現(xiàn)的次數(shù)，第二個map存儲該元素第一次出現(xiàn)的位置，第三個map存儲該元素最后一次出現(xiàn)的位置。

完整代碼

class Solution {
    public int findShortestSubArray(int[] nums) {
        HashMap<Integer, Integer> left = new HashMap(), right = new HashMap(), count = new HashMap();
        //count存儲次數(shù)、left存儲第一次位置、right存儲最后一次出現(xiàn)的位置
        int maxDegree = 0;//數(shù)組的度
        for (int i = 0; i < nums.length; i++) {
            if (count.containsKey(nums[i])) {
                count.put(nums[i], count.get(nums[i]) + 1);
            } else {
                count.put(nums[i], 1);
                left.put(nums[i], i);//第一次出現(xiàn)時存入left
            }
            maxDegree = Math.max(maxDegree, count.get(nums[i]));
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (!right.containsKey(nums[i])) {
                right.put(nums[i], i);//倒序遍歷第一次出現(xiàn)即為最后一次出現(xiàn)的位置
            }
        }
        int ans = nums.length;//所求的子數(shù)組最大為nums的長度
        for (int i : count.keySet()) {
            if (count.get(i) == maxDegree) {
                ans = Math.min(ans, right.get(i) - left.get(i) + 1);
            }
        }
        return ans;
    }

}

這道題給我的教訓主要是不要吝惜空間，有需要就用，太過扣的話就很容易做不出優(yōu)秀的題解；當然了，實際使用中時間和空間的權(quán)衡也是一項比較重要的問題，需要學習的東西還是很多啊。