LeetCode Hot 100 题解 - JavaScript

由于面试需要，决定从零开始刷 LeetCode Hot 100，记录一下刷题过程。

问题都很长，所以只记录题目和解题思路

准备

先简单了解下数据结构，很不错的视频

你是天才，所以不用学数据结构 | bilibili

然后上 LeetCode 注册账号，开始刷题。

哈希

1. 两数之和

最直接的是使用两层 for 循环，遍历判断两数之和是否等于 target，时间复杂度 O(n^2)

更好的思路是使用哈希表（Map），A + B = C，这里是去找 C - A 的值，如果这个值在哈希表中存在，就说明找到了 A 和 B，时间复杂度为 O(n)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map()

  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (map.has(need)) return [map.get(need), i]
    map.set(nums[i], i)
  }

  return []
}

49. 字母异位词分组

字母异位词就是两个单词的组成字母完全相同，如 abc 和 cba 是异位词

思路：对每个字符串字母排序，判断排序后字符串是否相等，然后对原字符进行分组

思路有了就找结构，要存原字符串，然后原字符串要对应排序后的字符串，所以哈希表（Map）最好不过了

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  const map = new Map()

  for (const s of strs) {
    const key = s.split('').sort().join('')
    if (!map.has(key)) {
      map.set(key, [])
    }
    map.get(key).push(s)
  }

  return [...map.values()]
}

128. 最长连续序列

思路：先对数组去重排序，存两个值：一个当前连续长度，一个最长连续长度，然后遍历一遍新数组，连续的就加当前长度，不连续就重置当前长度，最后返回最长长度

这里去重用的是 Set 结构，去除重复元素，排序用数组的 sort 方法。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0
  const snums = [...new Set(nums)].sort((a, b) => a - b)

  let current = 1
  let result = 1

  for (let i = 0; i < snums.length - 1; i++) {
    const a = snums[i]
    const b = snums[i + 1]

    if (b - a === 1) {
      current++
      result = Math.max(current, result)
    } else {
      current = 1
    }
  }

  return result
}

最开始漏掉了判断数组长度为 0 的情况，每道题都应该去考虑边界情况。

这个能够 AC（Accepted），但是时间复杂度是 O(n logn)，题目要求 O(n) 的时间复杂度，所以这个解法不符合要求。

看了题解，是在判断是否连续时，判断当前元素的上一个元素是否存在，如果不存在则说明当前元素是连续序列的起点，然后从当前元素去向后找连续的元素。

更改后：

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function (nums) {
  if (nums.length === 0) return 0

  const set = new Set(nums)
  let longest = 0

  for (const num of set) {
    // 连续起始
    if (!set.has(num - 1)) {
      let current = num
      let length = 1

      while (set.has(current + 1)) {
        current++
        length++
      }

      longest = Math.max(length, longest)
    }
  }

  return longest
}

双指针

283. 移动零

思路：将所有零后移，可以使用双指针，一个指针遍历数组，另一个指针记录非零元素位置，当遍历到非零元素时，将其放到非零元素位置指针上，然后指针后移，直到遍历完数组，最后将非零元素位置指针之后的元素全部设为 0。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let slow = 0

  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow] = nums[fast]
      slow++
    }
  }

  while (slow < nums.length) {
    nums[slow] = 0
    slow++
  }
}

15. 三数之和

虽然这个依然能暴力，但是 3 个 for 循环，时间复杂度飙到 O(n^3)了，所以还是要用双指针。

思路：固定一个数，然后使用双指针找另外两个数，跟 11. 盛最多水的容器 类似，两个指针向内移动。

容易漏的点是去重，外层 for 索引和两个指针都要去重。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const ans = []
  let snums = nums.sort((a, b) => a - b)

  for (let i = 0; i < snums.length; i++) {
    if (i > 0 && snums[i] === snums[i - 1]) continue
    const a = snums[i]
    let left = i + 1
    let right = snums.length - 1

    while (left < right) {
      const b = snums[left]
      const c = snums[right]
      const sum = a + b + c

      if (sum === 0) {
        ans.push([a, b, c])
        while (left < right && snums[left] === snums[left + 1]) left++
        while (left < right && snums[right] === snums[right - 1]) right--

        left++
        right--
      } else if (sum < 0) {
        left++
      } else {
        right--
      }
    }
  }

  return ans
}

42. 接雨水

思路：每个位置的雨水是被两侧围住的，能分析出来每个位置的雨水量 = min(左边最高高度, 右边最高高度) - 当前高度。

暴力解法是每个位置向两侧遍历找最高高度，时间复杂度 O(n^2)；稍微好一点的话，遍历一遍数组，用两个数组分别存储每个位置的左边最高高度和右边最高高度，然后再遍历一遍数组计算雨水量，时间复杂度 O(n)。

更好的办法是使用双指针，两个指针分别指向数组的两端，在线更新左右两侧的最高高度，移动较低的指针，直到两个指针相遇。因为从最左侧和从最右侧出发，对于一侧经过的位置是逐渐增加的，所以可以在线更新最高高度。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let l = 0
  let r = height.length - 1
  let leftMax = 0
  let rightMax = 0
  let ans = 0

  while (l < r) {
    if (height[l] <= height[r]) {
      if (height[l] >= leftMax) {
        leftMax = height[l]
      } else {
        ans += leftMax - height[l]
      }
      l++
    } else {
      if (height[r] >= rightMax) {
        rightMax = height[r]
      } else {
        ans += rightMax - height[r]
      }
      r--
    }
  }

  return ans
}

滑动窗口

3. 无重复字符的最长子串

思路：滑动窗口，[left, right]，找连续无重复最长子串，让 left 先固定，right 向右移动，right 移动过程用 Map 记录字符索引，这样当 right 移动到重复字符时，将 left 移动到重复字符的下一个位置，名副其实的 “滑动窗口”。

有个容易漏的点，移动 left 应该比较重复字符的索引和 left 当前大小，取最大值，这样才能保证 left 不会回退过去。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  if (s.length <= 1) return s.length
  let ans = 0
  const map = new Map()
  let left = 0

  for (let right = 0; right < s.length; right++) {
    if (map.has(s[right])) {
      left = Math.max(left, map.get(s[right]) + 1)
    }
    map.set(s[right], right)
    ans = Math.max(ans, right - left + 1)
  }

  return ans
}

438. 找到字符串中所有字母异位词

首先是最无脑打法：

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const n = p.length
  const target = p.split('').sort().join()
  let left = 0
  const ans = []

  for (let right = n - 1; right < s.length; right++) {
    if (
      s
        .slice(left, right + 1)
        .split('')
        .sort()
        .join() == target
    ) {
      ans.push(left)
    }
    left++
  }

  return ans
}

提交运行，超出时间限制，只好另寻方法

看了题解，使用滑动窗口的同时统计字符频次，一个 need Map + 一个 window Map + 一个 valid 计数器，滑动窗口的同时更新 window Map，然后对 valid++ 或 valid—，当 valid === need Map 大小 (need.size) 时，说明找到了一个异位词。

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const ans = []
  const need = new Map()
  const window = new Map()

  for (const ch of p) {
    need.set(ch, (need.get(ch) || 0) + 1)
  }

  let left = 0
  let right = 0
  let valid = 0

  while (right < s.length) {
    const ch = s[right]
    if (need.has(ch)) {
      window.set(ch, (window.get(ch) || 0) + 1)
      if (need.get(ch) === window.get(ch)) {
        valid++
      }
    }
    right++

    if (right - left === p.length) {
      if (valid === need.size && right - left === p.length) {
        ans.push(left)
      }

      const l = s[left]
      if (need.has(l)) {
        if (need.get(l) === window.get(l)) {
          valid--
        }
        window.set(l, window.get(l) - 1)
      }

      left++
    }
  }

  return ans
}

子串

560. 和为 K 的子数组

思路：前缀和 + 哈希表，遍历数组，计算前缀和 sum，同时把前缀和记录到哈希表，值是出现的次数，然后判断 sum - k 是否在哈希表中（看到了两数之和的影子），如果存在就 ans++。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  let ans = 0
  let sum = 0
  const map = new Map()
  map.set(0, 1)

  for (const num of nums) {
    sum += num
    const target = sum - k
    if (map.has(target)) {
      ans += map.get(target)
    }
    map.set(sum, (map.get(sum) || 0) + 1)
  }

  return ans
}

239. 滑动窗口最大值

~~休息一会～~ 休息完了，先来个暴力解法（bushi）

思路：又是新东西，这次用单调递减队列 q(ueue) 去获取最大值，最开始是用队列存的值，结果发现如果有重复值，删除的时候就会出问题，改成存索引简直完美。新增元素时，从队尾不断向前比较，然后填入元素，同时根据当前最大值的索引判断是否过期，在窗口成型后，每次推送 q[0] 的值到结果数组中。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const n = nums.length
  if (n === 0 || k === 0) return []

  const res = []
  const q = []

  for (let i = 0; i < n; i++) {
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop()
    }

    q.push(i)

    if (q[0] <= i - k) {
      q.shift()
    }

    if (i >= k - 1) {
      res.push(nums[q[0]])
    }
  }

  return res
}

思路：这一个跟找字母异位词类似…依旧使用滑动窗口 + 哈希表，统计字符频次，一个 need Map + 一个 window Map + 一个 valid 计数器，滑动窗口的同时更新 window Map，然后对 valid++ 或 valid—，当 valid === need Map 大小 (need.size) 时，说明找到了一个覆盖子串，然后左侧不断收缩，记录最小长度，直到 valid !== need.size 跳出循环，继续右侧扩张。

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  if (s.length === 0 || t.length > s.length) return ''

  const need = new Map()
  const window = new Map()
  let valid = 0

  let start = 0
  let minLen = Infinity

  for (const s of t) {
    need.set(s, (need.get(s) || 0) + 1)
  }

  let left = 0
  let right = 0
  while (right < s.length) {
    const b = s[right]

    if (need.has(b)) {
      window.set(b, (window.get(b) || 0) + 1)
      if (need.get(b) === window.get(b)) {
        valid++
      }
    }
    right++

    while (valid === need.size) {
      if (right - left < minLen) {
        minLen = right - left
        start = left
      }

      const a = s[left]
      if (need.has(a)) {
        if (window.get(a) === need.get(a)) {
          valid--
        }
        window.set(a, window.get(a) - 1)
      }
      left++
    }
  }

  if (minLen === Infinity) return ''
  return s.substring(start, start + minLen)
}

普通数组

53. 最大子数组和

思路：找到连续子数组最大的和，想到前缀和，这个和一定是一个前缀和减去前面最小的前缀和。那就很简单了，for 遍历一遍数组，计算前缀和 pre，同时记录最小前缀和 min，取 pre - min 的最大值。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let max = -Infinity
  let min = 0
  let pre = 0
  for (let i = 0; i < nums.length; i++) {
    pre += nums[i]
    max = Math.max(max, pre - min)
    min = Math.min(min, pre)
  }

  return max
}

还有一种思路是动态规划，dp[i] 表示以 nums[i] 结尾的最大子数组和，那么 dp[i] = max(dp[i - 1] + nums[i], nums[i])，也就是让当前元素加上前一个最大子数组和，与当前元素本身比较，取最大值。有点像走楼梯问题，走楼梯只能走一阶或者两阶，那么走最后一阶的时候一定是从倒数第二阶或倒数第一阶走上来的。

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
  let cur = nums[0]
  let res = nums[0]

  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(cur + nums[i], nums[i])
    res = Math.max(res, cur)
  }

  return res
}

56. 合并区间

思路：先对区间左端点排序，然后遍历区间数组，这里用 ans 存储合并后的区间。

这里有个点是 last 是对 ans 的最后一个数组元素的引用，直接修改 last[1] 就是修改了 ans 中的最后一个区间。~~原本一股脑写了 ans.pop()，然后再 push()~~

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  if (intervals.length === 0) return []

  const ans = []
  intervals.sort((a, b) => a[0] - b[0])
  ans.push(intervals[0])

  for (let i = 1; i < intervals.length; i++) {
    const cur = intervals[i]
    const last = ans[ans.length - 1]

    if (cur[0] <= last[1]) {
      last[1] = Math.max(last[1], cur[1])
    } else {
      ans.push(cur)
    }
  }

  return ans
}

189. 轮转数组

思路：用一个额外数组存储轮转后的数组，很简单直接

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  const n = nums.length
  k = k % n
  const res = new Array(n)
  for (let i = 0; i < n; i++) {
    res[(i + k) % n] = nums[i]
  }
  for (let i = 0; i < n; i++) {
    nums[i] = res[i]
  }
}

看题解还有原地反转算法，空间复杂度为 O(1)，先将整个数组反转，然后将前 k 个元素反转，再将后 n - k 个元素反转。反转函数用的是双指针。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  const n = nums.length
  k = k % n
  if (k === 0) return

  const reverse = (arr, l, r) => {
    while (l < r) {
      const tmp = arr[l]
      arr[l] = arr[r]
      arr[r] = tmp
      l++
      r--
    }
  }

  reverse(nums, 0, n - 1)
  reverse(nums, 0, k - 1)
  reverse(nums, k, n - 1)
}

238. 除了自身以外数组的乘积

明天继续 = =

准备

哈希

双指针

滑动窗口

子串

普通数组

矩阵

链表

二叉树

图论

回溯

二分查找

栈

堆

贪心算法

动态规划

多维动态规划

技巧

评论

大家在聊 (0)