697. Degree of an Array

Given a non-empty array of non-negative integers `nums`, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of `nums`, that has the same degree as `nums`.

Example 1:

``````Input: [1, 2, 2, 3, 1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.
``````

Example 2:

``````Input: [1,2,2,3,1,4,2]
Output: 6
``````

Note:

• `nums.length` will be between 1 and 50,000.
• `nums[i]` will be an integer between 0 and 49,999.

``````class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
int n = nums.size(), res = INT_MAX, degree = 0;
unordered_map<int, int> m;
unordered_map<int, pair<int, int>> pos;
for (int i = 0; i < nums.size(); ++i) {
if (++m[nums[i]] == 1) {
pos[nums[i]] = {i, i};
} else {
pos[nums[i]].second = i;
}
degree = max(degree, m[nums[i]]);
}
for (auto a : m) {
if (degree == a.second) {
res = min(res, pos[a.first].second - pos[a.first].first + 1);
}
}
return res;
}
};
``````

``````class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
int n = nums.size(), res = INT_MAX, degree = 0;
unordered_map<int, int> m, startIdx;
for (int i = 0; i < n; ++i) {
++m[nums[i]];
if (!startIdx.count(nums[i])) startIdx[nums[i]] = i;
if (m[nums[i]] == degree) {
res = min(res, i - startIdx[nums[i]] + 1);
} else if (m[nums[i]] > degree) {
res = i - startIdx[nums[i]] + 1;
degree = m[nums[i]];
}
}
return res;
}
};
``````

Maximum Subarray

https://discuss.leetcode.com/topic/107097/java-o-n-time-o-n-space

https://discuss.leetcode.com/topic/107216/concise-c-solution-using-hash-map-o-n-time

http://www.cnblogs.com/grandyang/p/5265628.html

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation