字谜分组、三数之和、无重复字符的最长子串、矩阵置零和递增的三元子序列

字谜分组

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

示例

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

方法一 排序分类

思路

我们先遍历数组,把每个字母异位词都进行排序。再将排序后的字符串作为 key,将 key 值一样的字母异位词置于同一个数组中。最后,再按照题目所要求的格式返回数组。

详解

  1. 创建个空对象 obj,用于后续将字母异位词分类储存;

  2. 创建个空数组 arr,用与后续返回结果;

  3. 遍历数组里的元素;

  4. 将每个字母异位词进行排序,并将排序后的字符串作为 key,可知 key 值一样的即为字母异位词,将他们置于同一个数组中(即 obj["aet"] = ["ate","eat","tea"]);

  5. 待上述遍历结束,再遍历 obj,将 obj 的每一个值,push 到 arr 中。

代码

const groupAnagrams = function (strs) {
const obj = {};
const arr = [];
// 遍历数组
for (let i = 0; i < strs.length; i++) {
// 将每个字母异位词进行排序,并将排序后的字符串作为 key
const unit = Array.from(strs[i]).sort().join('');
// 将 key 值一样的字母异位词置于同一个数组中
if (!obj[unit]) {
obj[unit] = [];
}
obj[unit].push(strs[i]);
}
for (const i in obj) {
arr.push(obj[i]);
}
return arr;
};

复杂度分析

  • 时间复杂度: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)

Array.sort排序算法链接

方法二 计数分类

思路

我们先遍历数组,每次都创建一个长度为 26,元素全是 0 的数组,用于记录每个单词中每个字符出现的次数;然后将其转化为字符串作为 key,将 key 值一样的字母异位词置于同一个数组中。最后,再按照题目所要求的格式返回数组。

详解

1.创建个空对象 obj,用于后续将字母异位词分类储存;

2.创建个空数组 arr,用与后续返回结果;

3.遍历数组里的元素;

4.每次遍历都创建一个长度为 26(跟 26 个英文字母对应),元素全是 0 的数组,用于记录每个单词中每个字符出现的次数,然后将该数组转化的字符串作为 key,可知 key 值一样的即为字母异位词,将他们置于同一个数组中;

5.待上述遍历结束,再遍历 obj,将 obj 的每一个值,push 到 arr 中。

代码

const groupAnagrams = function (strs) {
const obj = {};
const arr = [];
// 遍历数组
for (let i = 0; i < strs.length; i++) {
// 都创建一个长度为 26,元素全是 0 的数组,用于记录每个单词中每个字符出现的次数
const unit = new Array(26).fill(0);
for (let j = 0; j < strs[i].length; j++) {
const index = strs[i].charCodeAt(j) - 97;
unit[index] += 1;
}
// 将每个数组转化的字符串作为 key
const newUnit = JSON.stringify(unit);
// 将 key 值一样的字母异位词置于同一个数组中
if (!obj[newUnit]) {
obj[newUnit] = [];
}
obj[newUnit].push(strs[i]);
}
for (const i in obj) {
arr.push(obj[i]);
}
return arr;
};

复杂度分析

  • 时间复杂度: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 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

方法一 暴力法

思路

我们首先想到的是三重循环,题目中要求三元组不能重复,因此对每次插入数组对三元组做一下简单的记录。

详解

直接对数组进行3重遍历,当三个数的和等于 0 时,插入数组,同时对已经插入对数据做一下记录

const threeSum = function (nums) {
const res = [];
const uniqueMap = {};
nums.sort();
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const item = [nums[i], nums[j], nums[k]];
if (!uniqueMap[item.join(',')]) {
res.push(item);
uniqueMap[item.join(',')] = 1;
}
}
}
}
}
return res;
};

复杂度分析

  • 时间复杂度:O(n3)O(n^3)

    解法虽然简单,套三重循环,时间复杂度高。

  • 空间复杂度:O(n)O(n)

    额外申请了uniqueMap的空间,复杂度为 O(n)O(n)

方法二 双指针

思路

首先对数组进行排序,便于在插入的时候去重,进行双指针遍历时,遇到重复的数就可以很方便得跳过。

详解

先将数组排序,令左指针L=i+1L = i + 1,右指针R=n1R = 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]是否重复,去重复解之后,同时将 LLRR 移到下一个位置

  • sumsum 小于 0,说明 nums[L]nums[L] 太小,LL 需要右移,L++L++

  • sumsum 大于 0,说明 nums[R]nums[R] 太大,RR 需要左移, RR--

const threeSum = function (nums) {
const res = [];
nums.sort((a, b) => a - b);
const length = nums.length;
for (let i = 0; i < length; i++) {
let left = i + 1;
let right = length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
res.push([nums[i], nums[left], nums[right]]);
const leftValue = nums[left];
// 这两步是为了去重
while (left < length && nums[left] === leftValue) {
left++;
}
const rightValue = nums[right];
while (right > left && nums[right] === rightValue) {
right--;
}
} else if (sum < 0) {
// 小于 0 说明太小了,需要向右移动
left++;
} else {
// 太大了,把右边的指针向左移动
right--;
}
}
while (i + 1 < nums.length && nums[i] === nums[i + 1]) {
i++;
}
}
return res;
};

复杂度分析

  • 时间复杂度: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

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例2

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例3

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

方法一

维护一个数组,数组里从前到后存放着字符。 在遍历过程中,维持数组中字符不重复,如果重复,则从数组中 shift 出字符, 直到移除那个重复字符为止,并记录下数组的最长长度。

思路

用一个数组来储存当前字符, 在遍历过程中不断地存入不重复字符,遇到重复字符则整理数组达到字符不重复的条件。

详解

初始化一个数组和最大值, 从前向后遍历字符串, 如果该字符不在数组中,则把字符 push 到数组中,并且比较记录下当前最大值。 否则就从头部向外 pop 字符直到该重复字符被移除, 如此循环直到结束。

const lengthOfLongestSubstring = function (s) {
let current = 0;
let max = 0;
const list = [];
const len = s.length;
for (; current < len; current++) {
if (list.indexOf(s[current]) === -1) {
list.push(s[current]);
} else {
do {
list.shift();
} while (list.indexOf(s[current]) !== -1);
list.push(s[current]);
}
max = Math.max(list.length, max);
}
return max;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    这样子需要从前向后遍历一遍长度为 nn 的字符串,需要进行n n 次字符是否重复的比较。

  • 空间复杂度:O(n)O(n)

    在计算比较过程中,数组最长有可能存放 nn 个不重复字符串。

方法二

从前到后遍历字符串,维护一个string,记录着不重复字符子串。 每当遇到重复的字符时候,找到string中重复的字符,并截断。 循环往复直到遍历最后一个字符.

思路

记录当前正在遍历的不重复字串的子集 string , 在遍历过程中不断地添加不重复字符,遇到重复字符则截断 string 达到 string 内补字符不重复的条件。

详解

  1. 初始化一个 string 和最大值,

  2. 从前向后遍历字符串,

  3. 如果该字符不在 string 中,则添加字符到 string 中,并记录下最大值。

  4. 否则就截断字符串,如此循环直到结束。

const lengthOfLongestSubstring = function (s) {
let num = 0;
let max = 0;
let subString = '';
for (char of s) {
if (subString.indexOf(char) === -1) {
subString += char;
num++;
max = max < num ? num : max;
} else {
subString += char;
subString = subString.slice(subString.indexOf(char) + 1);
num = subString.length;
}
}
return max;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    我们只遍历了包含有 nn 个元素的字符串一次。

  • 空间复杂度:O(n)O(n)

    所需的额外空间取决于子串的长度,子串始终小于等于传入字符串的长度,该子串最多需要存储 nn 个元素。

矩阵置零

给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法

示例 1

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

示例 2

输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

进阶

  • 一个直接的解决方案是使用 O(mn)O(mn) 的额外空间,但这并不是一个好的解决方案。

  • 一个简单的改进方案是使用 O(m+n) O(m + n) 的额外空间,但这仍然不是最好的解决方案。

  • 你能想出一个常数空间的解决方案吗?

注意事项

  1. 注意边遍历边修改原数组,以免未遍历元素受 0 值的影响。

方法一 记录 0 的位置

思路

申请额外空间去记录需要置为 0 的行号和列号

详解

  1. 申请 O(m+n)O(m+n) 的额外空间,声明两个数组,所占空间最大值分别为 mmnn,分别存放水平方向、垂直方向应该重置为零的元素下标

  2. 从上到下,从左到右依次遍历原数组,记录元素为 0 的横坐标与纵坐标到提前声明的两个需置零的数组

  3. 待遍历结束后,再次遍历原数组,按照两个需置零的数组把元素置为零。

const setZeroes = function (matrix) {
const len = matrix.length;
const width = matrix[0].length;
const vertical = [];
const horizontal = [];
for (let i = 0; i < len; i++) {
for (let j = 0; j < width; j++) {
if (!matrix[i][j]) {
vertical.push(j);
horizontal.push(i);
}
}
}
for (let i = 0; i < len; i++) {
if (horizontal.indexOf(i) > -1) {
matrix[i].fill(0, 0, width);
}
for (let j = 0; j < vertical.length; j++) {
matrix[i][vertical[j]] = 0;
}
}
};

复杂度分析:

  • 时间复杂度: O(mn)O(m * n)

    算法包括两个遍历,运行次数为是 mnm * n所以时间复杂度是 O(mn)O(m * n)

  • 空间复杂度:O(m+n)O(m+n)

    额外空间包括若干个常量和两个长度分别为 mmnn的数组

方法二 原地算法

思路

我们不能再额外创建数组来记录 0 的位置,从原数组本身找突破点,用原数组的第一行和第一列记录该行或该列需不需要置零,再根据首行首列的标识对元素置零

参考图

详解

  1. 首先从左到右,从上到下遍历数组中每一个元素(列遍历从第二列开始),若该元素为 0,则同时设置改行首列元素、首行该列元素为 0,若首列存在为 0 元素,则设置标识,意为首列元素会被全部置零,此目的是区分行元素与首列元素置零的标识,

  2. 然后,从右到左,从下到上遍历数组,若首行该列或该行首列元素为 0,则置该元素为 0,若存在标识,则置首列元素为 0,为什么不选择从左到右,从上到下遍历?是因为首行首列的先根据标志置零,新的零元素会影响后面的数据。

const setZeroes = function (matrix) {
const len = matrix.length;
const width = matrix[0].length;
let flag = false;
for (let i = 0; i < len; i++) {
if (!matrix[i][0]) {
flag = true;
}
for (let j = 1; j < width; j++) {
if (!matrix[i][j]) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (let i = len - 1; i >= 0; i--) {
for (let j = width - 1; j > 0; j--) {
if (!matrix[0][j] || !matrix[i][0]) {
matrix[i][j] = 0;
}
}
if (flag) {
matrix[i][0] = 0;
}
}
};

复杂度分析:

  • 时间复杂度:O(mn)O(mn)

    算法包括两个遍历,运行次数都是 mnmn,所以时间复杂度是 O(mn)O(mn)

  • 空间复杂度:O(1)O(1)

    额外空间包括若干个常量,与 mmnn大小无关

递增的三元子序列

给定一个未排序的数组,判断这个数组中是否存在长度为 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, 2, 3, 4, 5];
输出: true;

示例 2:

输入: [5, 4, 3, 2, 1];
输出: false;

方法一 不连续的递增

思路

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

详解

  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。

/**
* @param {number[]} nums
* @return {boolean}
*/
const increasingTriplet = function (nums) {
if (nums.length < 3) return false;
let one,
two;
for (const num of nums) {
if (num > two) {
return true;
} else if (num > one) {
two = num;
} else {
one = num;
}
}
return false;
};

复杂度分析

  • 时间复杂度:O(n)O(n),遍历了1次含nn个元素的空间

  • 空间复杂度:O(1)O(1),遍历过程没有用到新的空间存储数据

方法二 贪心算法

思路

循环遍历数组,不断更新数组内出现的最小值与最大值,如果出现的一个大于最大值的数,则表示存在长度为 3 的递增子序列。

详解

  1. 若目标数组 nums 存在递增的三元子序列,设这三个数为 a1,a2,a3,则 a3>a2>a1

  2. 可以先定义两个变量 small, big (samll < big) 分别用于存放最小的两个数字,在js中使用 Number.MAX_SAFE_INTEGER 常量表示最大的安全整数(maxinum safe integer)(2^53 - 1)。

  3. 遍历数组,实时捕获当前最小的两个数,同时判断在这两个数后方是否存在一个数字a3>small && a3>big,若存在,即该数组存在长度为3的递增的子序列。

/**
* @param {number[]} nums
* @return {boolean}
*/
const increasingTriplet = function (nums) {
let small = Number.MAX_SAFE_INTEGER;
let big = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < nums.length; i++) {
if (nums[i] <= small) {
small = nums[i];
} else if (nums[i] <= big) {
big = nums[i];
} else {
return true;
}
}
return false;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    遍历了 1 次含 nn 个元素的空间

  • 空间复杂度:O(1)O(1)

    遍历过程没有用到新的空间存储数据