基本思路
需要知道数组中某些元素的出现次数来寻求最大出现次数,以及要找到长度最短的子数组长度。
因此可以考虑使用哈希表来记录某个元素出现的次数,第一个元素出现的下表,最后一个元素出现的下标。映射关系:x-->{times,starti,endj}。
标程
1 class Solution { 2 public: 3 int findShortestSubArray(vector<int>& nums) { 4 int n = nums.size(); 5 unordered_map <int, vector<int>> mp; 6 for(int i = 0; i < n; i++){ 7 if(mp.count(nums[i])){ 8 mp[nums[i]][0]++; 9 mp[nums[i]][2] = i; 10 }else{ 11 mp[nums[i]]={1,i,i}; 12 } 13 } 14 int Max_degree = 0, Min_len = 0; 15 for(auto& [_,vec] : mp){ 16 if(vec[0] > Max_degree){ 17 Max_degree = vec[0]; 18 Min_len = vec[2] - vec[1] + 1; 19 } 20 else if(vec[0] == Max_degree){ 21 if(vec[2] - vec[1] + 1 < Min_len){ 22 Min_len = vec[2] - vec[1] + 1; 23 } 24 } 25 } 26 return Min_len; 27 } 28 };
时间复杂度
O(N)