本文主要记录了博主的 Leetcode 算法刷题记录，方便以后查询复习。

哈希表

两数之和

LeetCode 原题链接：1. 两数之和

这道题首先考虑的是通过两层for循环遍历查询，但这样有很多无意义的查找。因此我们可以采用哈希表来减少查找的时间复杂度，此时查找顺序是往后而不是往前。注意使用Map对象来减少查询之前数据的时间复杂度，这里不能使用WeakMap，因为WeakMap只能使用对象作为键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(target - nums[i])) {
      return [map.get(target - nums[i]), i];
    }
    if (!map.has(nums[i])) {
      map.set(nums[i], i);
    }
  }
};

console.log(twoSum([2, 7, 11, 15], 9));
// [ 0, 1 ]

字母异位词分组

LeetCode 原题链接：49. 字母异位词分组

建立一个判断某一字符串是否是同一组的函数，再遍历数组，填充键-数组的Map对象，然后利用Map对象的相关方法返回实例。关键在于如何判断是同一种类型的字符串，一种是将字符串转为数组后排序，然后生成唯一的key，排序算法时间复杂度 $O(nlogn)$ 另一种方法是使用一个26位的数组来构造一个字符串的唯一键，来实现匹配的目的，注意使用的是charCodeAt方法，此种方法的时间复杂度为 $O(n)$，$n$ 为字符串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = (strs) => {
  const valToKey = (str) => {
    const strArr = Array.from(str);
    return strArr.sort().toString();
  };
  const map = new Map();
  for (const str of strs) {
    const key = valToKey(str);
    if (!map.has(key)) {
      map.set(key, [str]);
    } else {
      map.get(key).push(str);
    }
  }
  return Array.from(map.values());
};

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
const groupAnagrams = (strs) => {
  const map = new Map();
  const valToKey = (str) => {
    const keyArr = new Array(26).fill(0);
    for (const char of str) {
      keyArr[char.charCodeAt() - "a".charCodeAt()]++;
    }
    return keyArr.toString();
  };
  for (const str of strs) {
    const key = valToKey(str);
    if (map.has(key)) {
      map.get(key).push(str);
    } else {
      map.set(key, [str]);
    }
  }
  return Array.from(map.values());
};

console.log(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]));
// [ [ 'eat', 'tea', 'ate' ], [ 'tan', 'nat' ], [ 'bat' ] ]

最长连续序列

LeetCode 原题链接：128. 最长连续序列

首先采用以数组为参数构建set，在建立每个元素哈希的同时去重，后续遍历在set集合中展开，然后找到每段区间的起始位置并求其最大值，即存在比起小的数字即set.has(num - 1)这种情况需要跳过，因为必然会从比num - 1开始遍历的区间的长度要小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {number}
 */
const longestConsecutive = (nums) => {
  const set = new Set(nums);
  let maxLength = 0;
  for (let num of set) {
    if (set.has(num - 1)) {
      continue;
    } else {
      let count = 1;
      while (set.has(++num)) {
        count++;
      }
      maxLength = Math.max(maxLength, count);
    }
  }
  return maxLength;
};

console.log(longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]));
// 9

总结

在 JS 中，哈希表主要采用Map和Set这两种内置的数据结构。合理使用这两种数据结构可以极大地方便查找元素，从而降低算法的时间复杂度。对于Map对象来说更是可以把键与值关联起来存储，方便算法的改进，还可以用于实际需求，如分组的运用。

双指针

移动零

LeetCode 原题链接：283. 移动零

代码中left指针指向已处理好的数组的末尾后一个元素，即指向现数组的第一个0，当right指针指向非零数字的时候就将非零数字提到前面然后进行交换。核心思路为left指针始终指向第一个0元素，当right指针指向遇到非零元素时left指针才会变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const moveZeroes = (nums) => {
  let left = 0,
    right = 0;
  while (right < nums.length) {
    if (nums[right] !== 0) {
      if (right > left) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
      }
      left++;
    }
    right++;
  }
};

const nums = [0, 1, 0, 3, 12];
moveZeroes(nums);
console.log(nums);
// [ 1, 3, 12, 0, 0 ]

盛水最多的容器

LeetCode 原题链接：11. 盛最多水的容器

双指针向内遍历，由于横向长度的变小，想要大于之前的水量，只能遇到更高的容器壁，所以小的容器壁一边需要往内收缩，不断更新最大值，最后得到相应的结果。感觉核心的思想还是贪心。🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
  let max = 0,
    left = 0,
    right = height.length - 1;
  while (left < right) {
    max =
      height[left] > height[right]
        ? Math.max(max, (right - left) * height[right--])
        : Math.max(max, (right - left) * height[left++]);
  }
  return max;
};

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));
// 49

三数之和

LeetCode 原题链接：15. 三数之和

这道题目的难点在于去重。将数组进行排序是一个很巧妙的做法，一方面可以便于第一层i使用一次后去重，第二个是便于l和r双指针向内遍历去重，同时在nums[i] > 0的时候可以退出循环，避免无用的计算。做这道题重点在于两次去重的过程，值得仔细理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = (nums) => {
  if (!nums || nums.length < 3) {
    return [];
  }
  const res = [];
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > 0) {
      break;
    }
    while (i > 0 && nums[i] === nums[i - 1]) {
      i++;
    }
    let left = i + 1,
      right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        res.push([nums[i], nums[left], nums[right]]);
        while (nums[left] === nums[left + 1]) {
          left++;
        }
        while (nums[right] === nums[right - 1]) {
          right--;
        }
        left++;
        right--;
      } else if (sum > 0) {
        right--;
      } else {
        left++;
      }
    }
  }
  return res;
};

console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [ [ -1, -1, 2 ], [ -1, 0, 1 ] ]

接雨水

LeetCode 原题链接：42. 接雨水

接雨水似乎是写烂了的动态规划？🤔 下面也列出了三种方法，分别是：

  • 动态规划双向遍历得到左右数组，然后逐个元素求解。
  • 单调栈求解。注意栈中存储的是数组的索引。
  • 动态规划 + 双指针，两边取最小求解，leftMax和rightMax那个最小就确定了那个最小的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * @param {number[]} height
 * @return {number}
 */
const trap = (height) => {
  if (height.length < 3) {
    return 0;
  }
  const n = height.length;
  const leftMaxArr = new Array(n);
  leftMaxArr[0] = height[0];
  leftMaxArr[n - 1] = height[n - 1];
  for (let i = 1; i < n - 1; i++) {
    leftMaxArr[i] = Math.max(leftMaxArr[i - 1], height[i - 1]);
  }

  const rightMaxArr = new Array(n);
  rightMaxArr[0] = height[0];
  rightMaxArr[n - 1] = height[n - 1];
  for (let i = n - 2; i > 0; i--) {
    rightMaxArr[i] = Math.max(rightMaxArr[i + 1], height[i + 1]);
  }

  let res = 0;
  for (let i = 1; i < n - 1; i++) {
    const num = Math.min(leftMaxArr[i], rightMaxArr[i]);
    if (num > height[i]) {
      res += Math.abs(num - height[i]);
    }
  }
  return res;
};

/**
 * @param {number[]} height
 * @return {number}
 */
const trap = (height) => {
  let res = 0;
  const stack = [];
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop();
      if (!stack.length) {
        break;
      }
      const left = stack[stack.length - 1];
      const curHeight = Math.min(height[left], height[i]) - height[top];
      const curWidth = i - left - 1;
      res += curWidth * curHeight;
    }
    stack.push(i);
  }
  return res;
};

/**
 * @param {number[]} height
 * @return {number}
 */
const trap = (height) => {
  let res = 0;
  let left = 0,
    right = height.length - 1;
  let leftMax = 0,
    rightMax = 0;
  while (left < right) {
    leftMax = Math.max(height[left], leftMax);
    rightMax = Math.max(height[right], rightMax);
    if (leftMax < rightMax) {
      res += leftMax - height[left];
      left++;
    } else {
      res += rightMax - height[right];
      right--;
    }
  }
  return res;
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));
// 6

总结

双指针向内收缩对于特殊情况的元素遍历有很大的帮助，对于两个或两个以上元素的遍历，都可以考虑双指针的做法。

滑动窗口

无重复字符的最长字串

LeetCode 原题链接：3. 无重复字符的最长子串

利用set集合与滑动窗口解决，右扩张，左收缩，遍历数组获得最长长度。有点像滑动窗口 + 哈希表 + 双指针的结合。🤩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
const lengthOfLongestSubstring = (s) => {
  const set = new Set();
  let i = 0,
    maxLength = 0;
  for (const char of s) {
    while (set.has(char)) {
      set.delete(s[i++]);
    }
    set.add(char);
    maxLength = Math.max(maxLength, set.size);
  }
  return maxLength;
};

console.log(lengthOfLongestSubstring("abcabcbb"));
// 3

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

LeetCode 原题链接：438. 找到字符串中所有字母异位词

主要采取长度为26位的数组生成唯一的key值，用来滑动窗口进行匹配。注意对一个元素进行处理或者对最后增减做一个条件判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
const findAnagrams = (s, p) => {
  if (p.length > s.length) {
    return [];
  }
  const pKeyArr = new Array(26).fill(0);
  for (const char of p) {
    pKeyArr[char.charCodeAt() - "a".charCodeAt()]++;
  }
  const pKey = pKeyArr.toString();
  const winArr = new Array(26).fill(0);
  for (let i = 0; i < p.length; i++) {
    winArr[s[i].charCodeAt() - "a".charCodeAt()]++;
  }
  const res = [];
  for (let i = 0; i < s.length - p.length + 1; i++) {
    if (winArr.toString() === pKey) {
      res.push(i);
    }
    if (i + p.length < s.length) {
      winArr[s[i].charCodeAt() - "a".charCodeAt()]--;
      winArr[s[i + p.length].charCodeAt() - "a".charCodeAt()]++;
    }
  }
  return res;
};

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
const findAnagrams = (s, p) => {
  if (s.length < p.length) {
    return [];
  }
  const keyArr = new Array(26).fill(0);
  const valArr = new Array(26).fill(0);
  const res = [];
  for (let i = 0; i < p.length; i++) {
    keyArr[p[i].charCodeAt() - "a".charCodeAt()]++;
    valArr[s[i].charCodeAt() - "a".charCodeAt()]++;
  }
  const key = keyArr.toString();
  if (valArr.toString() === key) {
    res.push(0);
  }

  for (let i = p.length; i < s.length; i++) {
    valArr[s[i].charCodeAt() - "a".charCodeAt()]++;
    valArr[s[i - p.length].charCodeAt() - "a".charCodeAt()]--;
    if (valArr.toString() === key) {
      res.push(i - p.length + 1);
    }
  }
  return res;
};

console.log("cbaebabacd", "abc");
// [ 0, 6 ]

总结

滑动窗口分为静态大小的窗口和动态大小的窗口，前者每次都需要变化，大小固定；后者一般为右扩张左收缩，大小不固定。

子串

和为 k 的子数组

LeetCode 原题链接：560. 和为 k 的子数组

注意是连续的子数组，可以采用两层for循环，内层for循环往回遍历。或者使用哈希表，注意哈希表的思路比较巧妙，遍历到当前元素的时候，采取看之前的Map对象中是否存在当前和减去目标值，即map.has(pre - k)，存在即计数增加，注意需要设置0的初始值const map = new Map([[0, 1]])。暴力做法可帮助理解第二种做法 🦀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const subarraySum = (nums, k) => {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j >= 0; j--) {
      sum += nums[j];
      if (sum === k) {
        count++;
      }
    }
  }
  return count;
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
const subarraySum = (nums, k) => {
  let count = 0,
    pre = 0;
  const map = new Map([[0, 1]]);
  for (const num of nums) {
    pre += num;
    if (map.has(pre - k)) {
      count += map.get(pre - k);
    }
    if (map.has(pre)) {
      map.set(pre, map.get(pre) + 1);
    } else {
      map.set(pre, 1);
    }
  }
  return count;
};

console.log(subarraySum([1, 1, 1], 2));
// 2

滑动窗口最大值

LeetCode 原题链接：438. 找到字符串中所有字母异位词

有点类似单调栈？🤔 采用单调队列求解，但需要注意无论是队列还是栈，数组中存放的都是下标，推入的元素需要根据题目条件来做处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = (nums, k) => {
  const queue = [];
  for (let i = 0; i < k; i++) {
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop();
    }
    queue.push(i);
  }
  const res = [nums[queue[0]]];
  for (let i = k; i < nums.length; i++) {
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop();
    }
    queue.push(i);
    while (queue[0] <= i - k) {
      queue.shift();
    }
    res.push(nums[queue[0]]);
  }
  return res;
};

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [ 3, 3, 5, 5, 6, 7 ]

最小覆盖字串

LeetCode 原题链接：76. 最小覆盖字串

采用哈希表计数，然后采用不定长度滑动窗口求解，右扩张，左收缩，哈希表计数是关键中的关键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
const minWindow = (s, t) => {
  const map = new Map();
  for (const char of t) {
    map.set(char, map.has(char) ? map.get(char) + 1 : 1);
  }
  // 注意 count 不是 t 的长度而是不同字母的个数，即 Map 对象的大小
  let count = map.size,
    i = 0,
    j = 0,
    res = "";
  while (j < s.length) {
    if (map.has(s[j])) {
      map.set(s[j], map.get(s[j]) - 1);
      if (map.get(s[j]) === 0) {
        count--;
        if (count === 0) {
          while (true) {
            if (map.has(s[i])) {
              if (map.get(s[i]) === 0) {
                break;
              } else {
                map.set(s[i], map.get(s[i]) + 1);
              }
            }
            i++;
          }

          if (j - i < res.length || res === "") {
            res = s.slice(i, j + 1);
          }
          map.set(s[i], map.get(s[i]) + 1);
          count++;
          i++;
        }
      }
    }
    j++;
  }
  return res;
};

console.log(minWindow("ADOBECODEBANC", "ABC"));
// BANC

总结

子串很多都与哈希表相关，注意总结题目经验求解，很多情况下可能用到滑动窗口，单调栈与单调队列的思想也很重要。

普通数组

最大子数组和

LeetCode 原题链接：53. 最大子数组和

比较简单的动态规划题目，若前面的pre小于 0 则直接舍去，防止拖累变小，感觉也有点贪心的思想在里面。🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
const maxSubArray = (nums) => {
  let pre = 0,
    maxAns = nums[0];
  for (const num of nums) {
    pre = Math.max(pre + num, num);
    maxAns = Math.max(pre, maxAns);
  }
  return maxAns;
};

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
// 6

合并区间

LeetCode 原题链接：56. 合并区间

简单的模拟策略但需要注意排序的时候，在前面的右侧值不一定最大，所以需要取二者的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
const merge = (intervals) => {
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [];
  for (const interval of intervals) {
    if (res.length === 0 || interval[0] > res[res.length - 1][1]) {
      res.push(interval);
    } else {
      res[res.length - 1][1] = Math.max(res[res.length - 1][1], interval[1]);
    }
  }
  return res;
};

console.log(
  merge([
    [1, 3],
    [2, 6],
    [8, 10],
    [15, 18],
  ])
);
// [ [ 1, 6 ], [ 8, 10 ], [ 15, 18 ] ]

轮转数组

LeetCode 原题链接：189. 轮转数组

可采用额外数组存储，或者数组反转进行解决。第一种方法比较常规，第二种方法技巧性强但便于记忆与理解。😊

操作 结果
原始数组 1 2 3 4 5 6 7
翻转所有元素 7 6 5 4 3 2 1
翻转 $ [0, k\bmod n - 1] $ 区间的元素 5 6 7 4 3 2 1
翻转 $ [k\bmod n, n - 1] $ 区间的元素 5 6 7 1 2 3 4 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const rotate = (nums, k) => {
  k = k % nums.length;
  const newArr = new Array(nums.length);
  for (let i = 0; i < nums.length; i++) {
    newArr[(i + k) % nums.length] = nums[i];
  }
  for (let i = 0; i < nums.length; i++) {
    nums[i] = newArr[i];
  }
};

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
const rotate = (nums, k) => {
  k = k % nums.length;
  const reverse = (i, j) => {
    while (i < j) {
      const temp = nums[i];
      nums[i] = nums[j];
      nums[j] = temp;
      i++;
      j--;
    }
  };
  reverse(0, nums.length - 1);
  reverse(0, k - 1);
  reverse(k, nums.length - 1);
};

console.log(rotate([1, 2, 3, 4, 5, 6, 7], 3));
// [
//   5, 6, 7, 1,
//   2, 3, 4
// ]

除自身以外数组的乘积

LeetCode 原题链接：238. 除自身以外数组的乘积

类似接雨水双向数组，可采取遍历的方式进行反向计算。可以最大程度上节省空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {number[]} nums
 * @return {number[]}
 */
const productExceptSelf = (nums) => {
  const leftArr = new Array(nums.length).fill(1);
  const rightArr = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    leftArr[i] = leftArr[i - 1] * nums[i - 1];
  }
  for (let i = nums.length - 2; i >= 0; i--) {
    rightArr[i] = rightArr[i + 1] * nums[i + 1];
  }
  const res = new Array(nums.length);
  for (let i = 0; i < nums.length; i++) {
    res[i] = leftArr[i] * rightArr[i];
  }
  return res;
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
const productExceptSelf = (nums) => {
  const ansArr = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    ansArr[i] = ansArr[i - 1] * nums[i - 1];
  }
  let right = 1;
  for (let i = nums.length - 1; i >= 0; i--) {
    ansArr[i] = right * ansArr[i];
    right *= nums[i];
  }
  return ansArr;
};

console.log(productExceptSelf([1, 2, 3, 4]));
// [ 24, 12, 8, 6 ]

缺失的第一个正数

LeetCode 原题链接：41. 缺失的第一个正数

原地哈希，将数组的值i与下标i - 1相对应，没有对应的元素证明是第一个缺失的正整数。注意第三个判断条件nums[i] !== nums[nums[i] - 1]添加一个nums判断可以应对数组中重复值的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * @param {number[]} nums
 * @return {number}
 */
const firstMissingPositive = (nums) => {
  let n = nums.length;
  for (let i = 0; i < n; i++) {
    if (nums[i] <= 0) {
      nums[i] = n + 1;
    }
  }

  for (let i = 0; i < n; i++) {
    let num = Math.abs(nums[i]);
    if (num <= n) {
      nums[num - 1] = -Math.abs(nums[num - 1]);
    }
  }

  for (let i = 0; i < n; i++) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  return n + 1;
};

/**
 * @param {number[]} nums
 * @return {number}
 */
const firstMissingPositive = (nums) => {
  for (let i = 0; i < nums.length; i++) {
    while (
      nums[i] > 0 &&
      nums[i] <= nums.length &&
      nums[i] !== nums[nums[i] - 1]
    ) {
      const temp = nums[nums[i] - 1];
      nums[nums[i] - 1] = nums[i];
      nums[i] = temp;
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1;
    }
  }
  return nums.length + 1;
};

console.log(firstMissingPositive([3, 4, -1, 1]));
// 2

总结

数组的技巧性比较强，一般会与模拟，动态规划，哈希表结合，需要灵活使用。

矩阵

矩阵置零

LeetCode 原题链接： 73. 矩阵置零

常规的遍历标记然后取值，可以优化一下空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
const setZeroes = (matrix) => {
  const rowSet = new Set();
  const colSet = new Set();
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (matrix[i][j] === 0) {
        if (!rowSet.has(i)) {
          rowSet.add(i);
        }
        if (!colSet.has(j)) {
          colSet.add(j);
        }
      }
    }
  }
  rowSet.forEach((item) => {
    for (let i = 0; i < matrix[0].length; i++) {
      matrix[item][i] = 0;
    }
  });
  colSet.forEach((item) => {
    for (let i = 0; i < matrix.length; i++) {
      matrix[i][item] = 0;
    }
  });
};

const matrix = [
  [0, 1, 2, 0],
  [3, 4, 5, 2],
  [1, 3, 1, 5],
];
setZeroes(matrix);
console.log(matrix);
// [
//   [0, 0, 0, 0],
//   [0, 4, 5, 0],
//   [0, 3, 1, 0],
// ];

螺旋矩阵

LeetCode 原题链接：54. 螺旋矩阵

核心思路为模拟，设置上下左右 4 个变量便于理解，for循环的时候采用变量命名的方式提醒自己是行还是列，同时注意left <= right && top <= bottom与left < right && top < bottom这两个判断条件的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
const spiralOrder = (matrix) => {
  if (!matrix.length || !matrix[0].length) {
    return [];
  }

  let left = 0,
    right = matrix[0].length - 1,
    top = 0,
    bottom = matrix.length - 1;
  const res = [];
  while (left <= right && top <= bottom) {
    for (let col = left; col <= right; col++) {
      res.push(matrix[top][col]);
    }
    for (let row = top + 1; row <= bottom; row++) {
      res.push(matrix[row][right]);
    }
    if (left < right && top < bottom) {
      for (let col = right - 1; col > left; col--) {
        res.push(matrix[bottom][col]);
      }
      for (let row = bottom; row > top; row--) {
        res.push(matrix[row][left]);
      }
    }
    [left, right, top, bottom] = [left + 1, right - 1, top + 1, bottom - 1];
  }
  return res;
};

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
console.log(spiralOrder(matrix));
// [
//   1, 2, 3, 6, 9,
//   8, 7, 4, 5
// ]

旋转图像

LeetCode 原题链接：48. 旋转图像

可以采用额外空间来一一对应，或者采用特殊技巧，上下反转后再对角线反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
const rotate = (matrix) => {
  const n = matrix.length;
  const matrix_new = new Array(n).fill(0).map(() => new Array(n).fill(0));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      matrix_new[j][n - i - 1] = matrix[i][j];
    }
  }
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      matrix[i][j] = matrix_new[i][j];
    }
  }
};

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
const rotate = (matrix) => {
  const length = matrix.length;
  const halfLen = Math.floor(length / 2);
  for (let i = 0; i < halfLen; i++) {
    for (let j = 0; j < length; j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[length - i - 1][j];
      matrix[length - i - 1][j] = temp;
    }
  }
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < i; j++) {
      const temp = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = temp;
    }
  }
};

const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
rotate(matrix);
console.log(matrix);
// [
//   [7, 4, 1],
//   [8, 5, 2],
//   [9, 6, 3],
// ];

搜索二维矩阵

LeetCode 原题链接：240. 搜索二维矩阵

定位到右上角，利用矩阵递增的性质，实现 Z 字形查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
const searchMatrix = (matrix, target) => {
  let x = 0,
    y = matrix[0].length - 1;
  while (x < matrix.length && y >= 0) {
    if (target < matrix[x][y]) {
      y--;
    } else if (target > matrix[x][y]) {
      x++;
    } else {
      return true;
    }
  }
  return false;
};

console.log(
  searchMatrix(
    [
      [1, 4, 7, 11, 15],
      [2, 5, 8, 12, 19],
      [3, 6, 9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30],
    ],
    5
  )
);
// true

总结

矩阵的题目比较考验技巧与空间思维，需要严格分清行坐标与列坐标，写的时候需要思路清晰，一步一步来。