Concise c++ solution using hash map. O(n) time


  • 4
    A

    Using two hash map.
    One records the starting index for the character.
    The other records the frequency of the character.

    Once a certain character's frequency is bigger than others. we update the variable len. When more than two character have the same frequency, just compare their length, choose the shorter one.

    class Solution {
    public:
        int findShortestSubArray(vector<int>& nums) {
            if (nums.size() < 2) return nums.size();
            int res = nums.size();
            unordered_map<int, int> startIndex, count;
            int len = nums.size(), fre = 0;
            for (int i = 0; i < nums.size() ;i++) {
                if (startIndex.count(nums[i]) == 0) startIndex[nums[i]] = i;
                count[nums[i]]++;
                if (count[nums[i]] == fre){
                    len = min(i - startIndex[nums[i]] + 1, len);
                }
                if (count[nums[i]] > fre){
                    len = i - startIndex[nums[i]] + 1;
                    fre = count[nums[i]];
                }
            }
            return len;
        }
    };
    

  • 0
    N

    Brilliant solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.