697.数组的度

链接：697.数组的度
难度：Easy
标签：数组、哈希表
简介：给定一个非空且只包含非负数的整数数组  nums，数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与  nums  拥有相同大小的度的最短连续子数组，返回其长度。

题解 1 - typescript

• 编辑时间：2021-02-20
• 执行用时：208ms
• 内存消耗：45.3MB
• 编程语言：typescript
• 解法介绍：读取到度后直接取头尾进行判断。

function findShortestSubArray(nums: number[]): number {
  const map = new Map<number, number>();
  nums.forEach(num => map.set(num, 1 + (map.get(num) ?? 0)));
  const degreeValue = Math.max(...map.values());
  const degreeList = [];
  for (const [k, v] of map) v === degreeValue && degreeList.push(k);
  return Math.min(...degreeList.map(num => nums.lastIndexOf(num) - nums.indexOf(num) + 1));
}

题解 2 - typescript

• 编辑时间：2021-02-20
• 执行用时：104ms
• 内存消耗：46.3MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function findShortestSubArray(nums: number[]): number {
  const indexMap = new Map<number, [number, number]>();
  const computeIndex = (num: number) => {
    const [start, end] = indexMap.get(num)!;
    return end - start + 1;
  };
  const map = new Map<number, number>();
  for (let i = 0, len = nums.length; i < len; i++) {
    const num = nums[i];
    map.set(num, 1 + (map.get(num) ?? 0));
    const indexes = indexMap.get(num);
    if (indexes) {
      indexes[1] = i;
    } else {
      indexMap.set(num, [i, i]);
    }
  }
  const degreeValue = Math.max(...map.values());
  const degreeList = [];
  for (const [k, v] of map) v === degreeValue && degreeList.push(k);
  return Math.min(...degreeList.map(num => computeIndex(num)));
}

题解 3 - typescript

• 编辑时间：2021-02-20
• 执行用时：100ms
• 内存消耗：44.4MB
• 编程语言：typescript
• 解法介绍：优化题解 1。

function findShortestSubArray(nums: number[]): number {
  const map: Record<number, [number, number, number]> = {};
  nums.forEach((num, i) => {
    const data = map[num];
    if (data) {
      data[0]++;
      data[2] = i;
    } else {
      map[num] = [1, i, i];
    }
  });
  const data = Object.values(map);
  const degreeValue = Math.max(...data.map(([c]) => c));
  return Math.min(
    ...data.filter(([c]) => c === degreeValue).map(([, start, end]) => end - start + 1)
  );
}