# 697. Degree of an Array

• Time: $O(n)$
• Space: $O(n)$
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: int findShortestSubArray(vector& nums) { int ans = 0; int degree = 0; unordered_map debut; unordered_map count; for (int i = 0; i < nums.size(); ++i) { const int num = nums[i]; if (!debut.count(num)) debut[num] = i; if (++count[num] > degree) { degree = count[num]; ans = i - debut[num] + 1; } else if (count[num] == degree) { ans = min(ans, i - debut[num] + 1); } } return ans; } };
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int findShortestSubArray(int[] nums) { int ans = 0; int degree = 0; Map debut = new HashMap<>(); Map count = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { final int num = nums[i]; debut.putIfAbsent(num, i); count.merge(num, 1, Integer::sum); if (count.get(num) > degree) { degree = count.get(num); ans = i - debut.get(num) + 1; } else if (count.get(num) == degree) { ans = Math.min(ans, i - debut.get(num) + 1); } } return ans; } }
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def findShortestSubArray(self, nums: List[int]) -> int: ans = 0 degree = 0 debut = {} count = collections.Counter() for i, num in enumerate(nums): debut.setdefault(num, i) count[num] += 1 if count[num] > degree: degree = count[num] ans = i - debut[num] + 1 elif count[num] == degree: ans = min(ans, i - debut[num] + 1) return ans