哈希表

面试中能用 hashMap 解答的题目往往会有更优的解法，但是 hashMap 是一种最容易想到也最容易实现的解法。

每日温度 (opens new window)

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

function dailyTemperatures(T: number[]): number[] {
  const n = T.length;
  if (!n) return [];
  const res = Array(T.length).fill(0);
  const stack: number[] = [];
  for (let i = n - 1; i >= 0; i--) {
    while (stack.length && T[i] >= T[stack[stack.length - 1]]) {
      stack.pop();
    }
    if (stack.length) res[i] = stack[stack.length - 1] - i;
    stack.push(i);
  }

  return res;
}

字母异位词分组 (opens new window)

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

function groupAnagrams(strs: string[]): string[][] {
  const sortStrs = new Set<string>(
    strs.map((value) => value.split("").sort().join(""))
  );
  const hashMap: { [key: string]: string[] } = {};
  sortStrs.forEach((value) => {
    hashMap[value] = [];
  });
  for (const str of strs) {
    const sortStr = str.split("").sort().join("");
    hashMap[sortStr].push(str);
  }
  return Object.values(hashMap);
}

和为 K 的子数组 (opens new window)

给定一个整数数组和一个整数 K，你需要找到该数组中和为 K 的连续子数组的个数

function subarraySum(nums: number[], k: number): number {
  const mp = new Map<number, number>();
  mp.set(0, 1);
  let count = 0,
    pre = 0;
  for (const x of nums) {
    pre += x;
    if (mp.has(pre - k)) count += mp.get(pre - k)!;
    if (mp.has(pre)) mp.set(pre, mp.get(pre)! + 1);
    else mp.set(pre, 1);
  }
  return count;
}

前 K 个高频元素 (opens new window)

给定一个非空数组，返回其中出现频率前 K 高的元素。

function topKFrequent(nums: number[], k: number): number[] {
  const hashMap: { [key: number]: number } = {};
  for (const num of nums) {
    hashMap[num] = hashMap[num] ?? 0;
    hashMap[num]++;
  }
  return Object.entries(hashMap)
    .sort(([__, a], [_, b]) => b - a)
    .map(([key]) => +key)
    .slice(0, k);
}

计算质数 (opens new window)

统计所有小于非负整数 n 的质数的数量

function countPrimes(n: number): number {
  const isPrimes = Array(n).fill(true)
  
  for(let i = 2; i * i < n; i++) {
    if(isPrimes[i]) {
      for(let j = i * i; j < n; j += i) {
        isPrimes[j] = false
      }
    }
  }
  
  let count = 0
  for(let i = 2; i < n; i++) {
    if(isPrimes[i]) count++
  }
  
  return count
}

无重复字符串的最长子串 (opens new window)

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

function lengthOfLongestSubstring(s: string): number {
  const n = s.length;
  let sub = "";
  let res = "";

  for (let i = 0; i < n; i++) {
    if (!sub) {
      sub += s[i];
      if (i === n - 1 && res.length < sub.length) res = sub;
    } else {
      if (!sub.includes(s[i])) {
        sub += s[i];
        if (i === n - 1 && res.length < sub.length) res = sub;
      } else {
        if (sub.length > res.length) res = sub;
        sub = sub.substr(sub.indexOf(s[i]) + 1) + s[i];
      }
    }
  }

  return res.length;
}