面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
数组
旋转数组、只出现一次的数字、两数之和、旋转图像
从排序数组中删除重复项、加一、买股票的最佳时机和移动零
两个数组的交集、一周中的第几天、有效的数独、除资深以外数组的乘积和存在重复元素
字谜分组、三数之和、无重复字符的最长子串、矩阵置零和递增的三元子序列
链表
二叉树
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
字谜分组、三数之和、无重复字符的最长子串、矩阵置零和递增的三元子序列

字谜分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例
1
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
2
输出:
3
[
4
["ate","eat","tea"],
5
["nat","tan"],
6
["bat"]
7
]
Copied!

方法一 排序分类

思路
我们先遍历数组，把每个字母异位词都进行排序。再将排序后的字符串作为 key，将 key 值一样的字母异位词置于同一个数组中。最后，再按照题目所要求的格式返回数组。
详解
  1. 1.
    创建个空对象 obj，用于后续将字母异位词分类储存；
  2. 2.
    创建个空数组 arr，用与后续返回结果；
  3. 3.
    遍历数组里的元素；
  4. 4.
    将每个字母异位词进行排序，并将排序后的字符串作为 key，可知 key 值一样的即为字母异位词，将他们置于同一个数组中（即 obj["aet"] = ["ate","eat","tea"]）；
  5. 5.
    待上述遍历结束，再遍历 obj，将 obj 的每一个值，push 到 arr 中。

代码

1
const groupAnagrams = function (strs) {
2
const obj = {};
3
const arr = [];
4
// 遍历数组
5
for (let i = 0; i < strs.length; i++) {
6
// 将每个字母异位词进行排序，并将排序后的字符串作为 key
7
const unit = Array.from(strs[i]).sort().join('');
8
// 将 key 值一样的字母异位词置于同一个数组中
9
if (!obj[unit]) {
10
obj[unit] = [];
11
}
12
obj[unit].push(strs[i]);
13
}
14
for (const i in obj) {
15
arr.push(obj[i]);
16
}
17
return arr;
18
};
Copied!
复杂度分析
  • 时间复杂度：
    O(nklogk)O(nklogk)
    ​
    外层 strs for 循环为
    O(n)O(n)
    ，里面根据字符数据进行排序，查资料得排序时间复杂度为
    O(kLogk)O(kLogk)
    ，k 为字符串长度最大值，即整个时间复杂度为
    O(nklogk)O(nklogk)
    。
  • 空间复杂度：
    O(nk)O(nk)
    ​
    代码运行时创建了 obj 对象用于存储 strs 中的字符串，空间与 strs 长度与字符串长度成正比关系，所以空间复杂度为
    O(nk)O(nk)
    。

方法二 计数分类

思路
我们先遍历数组，每次都创建一个长度为 26，元素全是 0 的数组，用于记录每个单词中每个字符出现的次数；然后将其转化为字符串作为 key，将 key 值一样的字母异位词置于同一个数组中。最后，再按照题目所要求的格式返回数组。
详解
1.创建个空对象 obj，用于后续将字母异位词分类储存；
2.创建个空数组 arr，用与后续返回结果；
3.遍历数组里的元素；
4.每次遍历都创建一个长度为 26（跟 26 个英文字母对应），元素全是 0 的数组，用于记录每个单词中每个字符出现的次数，然后将该数组转化的字符串作为 key，可知 key 值一样的即为字母异位词，将他们置于同一个数组中；
5.待上述遍历结束，再遍历 obj，将 obj 的每一个值，push 到 arr 中。
代码
1
const groupAnagrams = function (strs) {
2
const obj = {};
3
const arr = [];
4
// 遍历数组
5
for (let i = 0; i < strs.length; i++) {
6
// 都创建一个长度为 26，元素全是 0 的数组，用于记录每个单词中每个字符出现的次数
7
const unit = new Array(26).fill(0);
8
for (let j = 0; j < strs[i].length; j++) {
9
const index = strs[i].charCodeAt(j) - 97;
10
unit[index] += 1;
11
}
12
// 将每个数组转化的字符串作为 key
13
const newUnit = JSON.stringify(unit);
14
// 将 key 值一样的字母异位词置于同一个数组中
15
if (!obj[newUnit]) {
16
obj[newUnit] = [];
17
}
18
obj[newUnit].push(strs[i]);
19
}
20
for (const i in obj) {
21
arr.push(obj[i]);
22
}
23
return arr;
24
};
Copied!
复杂度分析
  • 时间复杂度：
    O(nk)O(nk)
    ​
外层 strs for 循环为
O(n)O(n)
，内层为对字符串进行 for 循环，时间复杂度为
O(k)O(k)
，k 为字符串长度最大值，即整个时间复杂度为
O(nk)O(nk)
。
  • 空间复杂度：
    O(nk)O(nk)
    ​
代码运行时创建了 obj 对象用于存储 strs 中的字符串，空间与 strs 长度与字符串长度成正比关系，所以空间复杂度为
O(nk)O(nk)
。

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例
1
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
2
​
3
满足要求的三元组集合为：
4
[
5
[-1, 0, 1],
6
[-1, -1, 2]
7
]
Copied!

方法一 暴力法

思路
我们首先想到的是三重循环，题目中要求三元组不能重复，因此对每次插入数组对三元组做一下简单的记录。
详解
直接对数组进行3重遍历，当三个数的和等于 0 时，插入数组，同时对已经插入对数据做一下记录
1
const threeSum = function (nums) {
2
const res = [];
3
const uniqueMap = {};
4
nums.sort();
5
for (let i = 0; i < nums.length - 2; i++) {
6
for (let j = i + 1; j < nums.length - 1; j++) {
7
for (let k = j + 1; k < nums.length; k++) {
8
if (nums[i] + nums[j] + nums[k] === 0) {
9
const item = [nums[i], nums[j], nums[k]];
10
if (!uniqueMap[item.join(',')]) {
11
res.push(item);
12
uniqueMap[item.join(',')] = 1;
13
}
14
}
15
}
16
}
17
}
18
return res;
19
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n3)O(n^3)
    ​
    解法虽然简单，套三重循环，时间复杂度高。
  • 空间复杂度：
    O(n)O(n)
    ​
    额外申请了uniqueMap的空间，复杂度为
    O(n)O(n)
    ​

方法二 双指针

思路
首先对数组进行排序，便于在插入的时候去重，进行双指针遍历时，遇到重复的数就可以很方便得跳过。
详解
先将数组排序，令左指针
L=i+1L = i + 1
，右指针
R=n−1R = n - 1
，当
L<=RL <= R
时，进行循环
  • 当
    nums[i]+nums[L]+nums[R]===0nums[i] + nums[L] + nums[R] === 0
     时，将三个数插入数组，同时判断
    nums[L]nums[L]
     和
    nums[L+1]nums[L + 1]
    是否重复，去重复解之后，同时将
    LL
     和
    RR
     移到下一个位置
  • 若
    sumsum
     小于 0，说明
    nums[L]nums[L]
     太小，
    LL
     需要右移，
    L++L++
    ​
  • 若
    sumsum
     大于 0，说明
    nums[R]nums[R]
     太大，
    RR
     需要左移,
    R−−R--
    ​
1
const threeSum = function (nums) {
2
const res = [];
3
nums.sort((a, b) => a - b);
4
const length = nums.length;
5
​
6
for (let i = 0; i < length; i++) {
7
let left = i + 1;
8
let right = length - 1;
9
while (left < right) {
10
const sum = nums[i] + nums[left] + nums[right];
11
if (sum === 0) {
12
res.push([nums[i], nums[left], nums[right]]);
13
​
14
const leftValue = nums[left];
15
​
16
// 这两步是为了去重
17
while (left < length && nums[left] === leftValue) {
18
left++;
19
}
20
const rightValue = nums[right];
21
while (right > left && nums[right] === rightValue) {
22
right--;
23
}
24
} else if (sum < 0) {
25
// 小于 0 说明太小了，需要向右移动
26
left++;
27
} else {
28
// 太大了，把右边的指针向左移动
29
right--;
30
}
31
}
32
while (i + 1 < nums.length && nums[i] === nums[i + 1]) {
33
i++;
34
}
35
}
36
return res;
37
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    数组遍历
    O(n)O(n)
    ，双指针遍历
    O(n)O(n)
    ，因此复杂度为
    O(n)∗O(n)O(n) * O(n)
     为
    O(n2)O(n^2)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    指针使用常数大小的额外空间

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例1
1
输入: "abcabcbb"
2
输出: 3
3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
Copied!
示例2
1
输入: "bbbbb"
2
输出: 1
3
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
Copied!
示例3
1
输入: "pwwkew"
2
输出: 3
3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
4
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
Copied!

方法一

维护一个数组，数组里从前到后存放着字符。 在遍历过程中，维持数组中字符不重复，如果重复，则从数组中 shift 出字符， 直到移除那个重复字符为止，并记录下数组的最长长度。
思路
用一个数组来储存当前字符， 在遍历过程中不断地存入不重复字符，遇到重复字符则整理数组达到字符不重复的条件。
详解
初始化一个数组和最大值， 从前向后遍历字符串， 如果该字符不在数组中，则把字符 push 到数组中，并且比较记录下当前最大值。 否则就从头部向外 pop 字符直到该重复字符被移除， 如此循环直到结束。
1
const lengthOfLongestSubstring = function (s) {
2
let current = 0;
3
let max = 0;
4
const list = [];
5
const len = s.length;
6
for (; current < len; current++) {
7
if (list.indexOf(s[current]) === -1) {
8
list.push(s[current]);
9
} else {
10
do {
11
list.shift();
12
} while (list.indexOf(s[current]) !== -1);
13
list.push(s[current]);
14
}
15
max = Math.max(list.length, max);
16
}
17
return max;
18
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    这样子需要从前向后遍历一遍长度为
    nn
     的字符串，需要进行
    n n
     次字符是否重复的比较。
  • 空间复杂度：
    O(n)O(n)
    ​
    在计算比较过程中，数组最长有可能存放
    nn
     个不重复字符串。

方法二

从前到后遍历字符串，维护一个string，记录着不重复字符子串。 每当遇到重复的字符时候，找到string中重复的字符，并截断。 循环往复直到遍历最后一个字符.
思路
记录当前正在遍历的不重复字串的子集 string ， 在遍历过程中不断地添加不重复字符，遇到重复字符则截断 string 达到 string 内补字符不重复的条件。
详解
  1. 1.
    初始化一个 string 和最大值，
  2. 2.
    从前向后遍历字符串，
  3. 3.
    如果该字符不在 string 中，则添加字符到 string 中，并记录下最大值。
  4. 4.
    否则就截断字符串，如此循环直到结束。
1
const lengthOfLongestSubstring = function (s) {
2
let num = 0;
3
let max = 0;
4
let subString = '';
5
for (char of s) {
6
if (subString.indexOf(char) === -1) {
7
subString += char;
8
num++;
9
max = max < num ? num : max;
10
} else {
11
subString += char;
12
subString = subString.slice(subString.indexOf(char) + 1);
13
num = subString.length;
14
}
15
}
16
return max;
17
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    我们只遍历了包含有
    nn
     个元素的字符串一次。
  • 空间复杂度：
    O(n)O(n)
    ​
    所需的额外空间取决于子串的长度，子串始终小于等于传入字符串的长度，该子串最多需要存储
    nn
     个元素。

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1
1
输入:
2
[
3
[1,1,1],
4
[1,0,1],
5
[1,1,1]
6
]
7
输出:
8
[
9
[1,0,1],
10
[0,0,0],
11
[1,0,1]
12
]
Copied!
示例 2
1
输入:
2
[
3
[0,1,2,0],
4
[3,4,5,2],
5
[1,3,1,5]
6
]
7
输出:
8
[
9
[0,0,0,0],
10
[0,4,5,0],
11
[0,3,1,0]
12
]
Copied!
进阶
  • 一个直接的解决方案是使用
    O(mn)O(mn)
     的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用
    O(m+n) O(m + n)
     的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗？
注意事项
  1. 1.
    注意边遍历边修改原数组，以免未遍历元素受 0 值的影响。

方法一 记录 0 的位置

思路
申请额外空间去记录需要置为 0 的行号和列号
详解
  1. 1.
    申请
    O(m+n)O(m+n)
     的额外空间，声明两个数组，所占空间最大值分别为
    mm
    ，
    nn
    ，分别存放水平方向、垂直方向应该重置为零的元素下标
  2. 2.
    从上到下，从左到右依次遍历原数组，记录元素为 0 的横坐标与纵坐标到提前声明的两个需置零的数组
  3. 3.
    待遍历结束后，再次遍历原数组，按照两个需置零的数组把元素置为零。
1
const setZeroes = function (matrix) {
2
const len = matrix.length;
3
const width = matrix[0].length;
4
const vertical = [];
5
const horizontal = [];
6
for (let i = 0; i < len; i++) {
7
for (let j = 0; j < width; j++) {
8
if (!matrix[i][j]) {
9
vertical.push(j);
10
horizontal.push(i);
11
}
12
}
13
}
14
for (let i = 0; i < len; i++) {
15
if (horizontal.indexOf(i) > -1) {
16
matrix[i].fill(0, 0, width);
17
}
18
for (let j = 0; j < vertical.length; j++) {
19
matrix[i][vertical[j]] = 0;
20
}
21
}
22
};
Copied!

复杂度分析：

  • 时间复杂度：
    O(m∗n)O(m * n)
    算法包括两个遍历，运行次数为是
    m∗nm * n
    ，所以时间复杂度是
    O(m∗n)O(m * n)
    ​
  • 空间复杂度：
    O(m+n)O(m+n)
    ​
    额外空间包括若干个常量和两个长度分别为
    mm
    ，
    nn
    的数组

方法二 原地算法

思路
我们不能再额外创建数组来记录 0 的位置，从原数组本身找突破点，用原数组的第一行和第一列记录该行或该列需不需要置零，再根据首行首列的标识对元素置零
参考图
详解
  1. 1.
    首先从左到右，从上到下遍历数组中每一个元素（列遍历从第二列开始），若该元素为 0，则同时设置改行首列元素、首行该列元素为 0，若首列存在为 0 元素，则设置标识，意为首列元素会被全部置零，此目的是区分行元素与首列元素置零的标识，
  2. 2.
    然后，从右到左，从下到上遍历数组，若首行该列或该行首列元素为 0，则置该元素为 0，若存在标识，则置首列元素为 0，为什么不选择从左到右，从上到下遍历？是因为首行首列的先根据标志置零，新的零元素会影响后面的数据。
1
const setZeroes = function (matrix) {
2
const len = matrix.length;
3
const width = matrix[0].length;
4
let flag = false;
5
for (let i = 0; i < len; i++) {
6
if (!matrix[i][0]) {
7
flag = true;
8
}
9
for (let j = 1; j < width; j++) {
10
if (!matrix[i][j]) {
11
matrix[i][0] = 0;
12
matrix[0][j] = 0;
13
}
14
}
15
}
16
for (let i = len - 1; i >= 0; i--) {
17
for (let j = width - 1; j > 0; j--) {
18
if (!matrix[0][j] || !matrix[i][0]) {
19
matrix[i][j] = 0;
20
}
21
}
22
if (flag) {
23
matrix[i][0] = 0;
24
}
25
}
26
};
Copied!
复杂度分析：
  • 时间复杂度：
    O(mn)O(mn)
    ​
    算法包括两个遍历，运行次数都是
    mnmn
    ，所以时间复杂度是
    O(mn)O(mn)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​
    额外空间包括若干个常量，与
    mm
    、
    nn
    大小无关

递增的三元子序列

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为
O(n)O(n)
，空间复杂度为
O(1)O(1)
 。
示例 1:
1
输入: [1, 2, 3, 4, 5];
2
输出: true;
Copied!
示例 2:
1
输入: [5, 4, 3, 2, 1];
2
输出: false;
Copied!

方法一 不连续的递增

思路
使用 one 和 two 两个数。保证 one 小于 two，若遍历到一个数大于 two，则满足3个数递增。返回true

详解

  1. 1.
    设置两个变量，one 代表三元子序列的第一个，two代表三元子序列的第二个。
例如：
  • 第一个数作为 one，第二个数若比第一个数大，这两个数可以成三元子序列中的前两个，于是可以赋值给two；
  • 第三个数比第二个数小，说明三元子序列可能会从这个数开始
    one、two 的初始值为 undefined，任意数与undefined做比较均为 false。
  • 现在，开始循环遍历 num，若：
  • num > two，说明可以构成三元子序列了，返回 true
  • num > one，说明 num 比 two 小（或等于），比 one 大，可以将 two 更新为此 num，
  • num < one，则这个 num 可以成为三元子序列的最小者，更新 one 为 num。
1
/**
2
* @param {number[]} nums
3
* @return {boolean}
4
*/
5
const increasingTriplet = function (nums) {
6
if (nums.length < 3) return false;
7
let one,
8
two;
9
for (const num of nums) {
10
if (num > two) {
11
return true;
12
} else if (num > one) {
13
two = num;
14
} else {
15
one = num;
16
}
17
}
18
return false;
19
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ，遍历了1次含
    nn
    个元素的空间
  • 空间复杂度：
    O(1)O(1)
    ，遍历过程没有用到新的空间存储数据

方法二 贪心算法

思路
循环遍历数组，不断更新数组内出现的最小值与最大值，如果出现的一个大于最大值的数，则表示存在长度为 3 的递增子序列。
详解
  1. 1.
    若目标数组 nums 存在递增的三元子序列，设这三个数为 a1,a2,a3,则 a3>a2>a1。
  2. 2.
    可以先定义两个变量 small, big (samll < big) 分别用于存放最小的两个数字，在js中使用 Number.MAX_SAFE_INTEGER 常量表示最大的安全整数（maxinum safe integer)（2^53 - 1）。
  3. 3.
    遍历数组，实时捕获当前最小的两个数，同时判断在这两个数后方是否存在一个数字a3>small && a3>big,若存在，即该数组存在长度为3的递增的子序列。
1
/**
2
* @param {number[]} nums
3
* @return {boolean}
4
*/
5
const increasingTriplet = function (nums) {
6
let small = Number.MAX_SAFE_INTEGER;
7
let big = Number.MAX_SAFE_INTEGER;
8
for (let i = 0; i < nums.length; i++) {
9
if (nums[i] <= small) {
10
small = nums[i];
11
} else if (nums[i] <= big) {
12
big = nums[i];
13
} else {
14
return true;
15
}
16
}
17
return false;
18
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    遍历了 1 次含
    nn
     个元素的空间
  • 空间复杂度：
    O(1)O(1)
    ​
    遍历过程没有用到新的空间存储数据
以前
两个数组的交集、一周中的第几天、有效的数独、除资深以外数组的乘积和存在重复元素
下一个
链表
最近更新 2yr ago
复制链接
内容
字谜分组
三数之和
无重复字符的最长子串
矩阵置零
递增的三元子序列