697. 数组的度
题目描述
输入一个非空的非负整数数组 nums。数组的度定义为其中出现次数最多的元素的出现次数。
在 nums 的所有连续子数组中，找出度与整个数组的度相等的那些，返回其中最短的长度。
示例 1
输入：nums = [1,2,2,3,1] 输出：2
解释：整个数组的度为 2（1 和 2 各出现两次），最短的是 [2,2]。
示例 2
输入：nums = [1,2,2,3,1,4,2] 输出：6
解释：2 出现 3 次，覆盖所有 2 的最短片段是 [2,2,3,1,4,2]。
数据范围
nums.length在1到50000之间。nums[i]是0到49999之间的整数。
解题思路
子数组要保持同样的度，就必须包含某个出现次数最多的元素的全部出现位置，最短就是从它第一次出现到最后一次出现的区间。所以用哈希表为每个值记录 [次数, 首次下标, 末次下标]，再在次数等于度的值里取区间长度 r-l+1 最小的。
为什么正确
info[x] = [x 的出现次数, 首次下标, 末次下标]；第二遍中 deg 是已看过的值的最大次数，best 是这些值中次数等于 deg 的最短区间长。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
度相同的元素可能有多个，要在它们之中取最短区间；只记第一个达到最大次数的元素会出错。区间长度是 r - l + 1，不要漏掉 +1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findShortestSubArray(self, nums: List[int]) -> int:
info = {}
for i, x in enumerate(nums):
if x in info:
info[x][0] += 1
info[x][2] = i
else:
info[x] = [1, i, i]
deg = best = 0
for cnt, l, r in info.values():
if cnt > deg:
deg, best = cnt, r - l + 1
elif cnt == deg:
best = min(best, r - l + 1)
return bestclass Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, int[]> info = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
if (info.containsKey(x)) {
info.get(x)[0]++;
info.get(x)[2] = i;
} else {
info.put(x, new int[]{1, i, i});
}
}
int deg = 0, best = 0;
for (int[] v : info.values()) {
int cnt = v[0], l = v[1], r = v[2];
if (cnt > deg) {
deg = cnt; best = r - l + 1;
} else if (cnt == deg) {
best = Math.min(best, r - l + 1);
}
}
return best;
}
}class Solution {
public:
int findShortestSubArray(vector<int>& nums) {
unordered_map<int, array<int, 3>> info;
for (int i = 0; i < (int)nums.size(); i++) {
int x = nums[i];
if (info.count(x)) {
info[x][0]++;
info[x][2] = i;
} else {
info[x] = {1, i, i};
}
}
int deg = 0, best = 0;
for (auto& [x, v] : info) {
int cnt = v[0], l = v[1], r = v[2];
if (cnt > deg) {
deg = cnt; best = r - l + 1;
} else if (cnt == deg) {
best = min(best, r - l + 1);
}
}
return best;
}
};func findShortestSubArray(nums []int) int {
info := map[int][]int{}
for i, x := range nums {
if v, ok := info[x]; ok {
v[0]++
v[2] = i
} else {
info[x] = []int{1, i, i}
}
}
deg, best := 0, 0
for _, v := range info {
cnt, l, r := v[0], v[1], v[2]
if cnt > deg {
deg, best = cnt, r-l+1
} else if cnt == deg {
if r-l+1 < best {
best = r - l + 1
}
}
}
return best
}var findShortestSubArray = function(nums) {
const info = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (info.has(x)) {
info.get(x)[0]++;
info.get(x)[2] = i;
} else {
info.set(x, [1, i, i]);
}
}
let deg = 0, best = 0;
for (const [cnt, l, r] of info.values()) {
if (cnt > deg) {
deg = cnt; best = r - l + 1;
} else if (cnt === deg) {
best = Math.min(best, r - l + 1);
}
}
return best;
};function findShortestSubArray(nums: number[]): number {
const info = new Map<number, number[]>();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (info.has(x)) {
info.get(x)![0]++;
info.get(x)![2] = i;
} else {
info.set(x, [1, i, i]);
}
}
let deg = 0, best = 0;
for (const [cnt, l, r] of info.values()) {
if (cnt > deg) {
deg = cnt; best = r - l + 1;
} else if (cnt === deg) {
best = Math.min(best, r - l + 1);
}
}
return best;
}