字谜分组、三数之和、无重复字符的最长子串、矩阵置零和递增的三元子序列
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],输出:[["ate","eat","tea"],["nat","tan"],["bat"]]
思路
我们先遍历数组，把每个字母异位词都进行排序。再将排序后的字符串作为 key，将 key 值一样的字母异位词置于同一个数组中。最后，再按照题目所要求的格式返回数组。
详解
创建个空对象 obj，用于后续将字母异位词分类储存；
创建个空数组 arr，用与后续返回结果；
遍历数组里的元素；
将每个字母异位词进行排序，并将排序后的字符串作为 key，可知 key 值一样的即为字母异位词，将他们置于同一个数组中（即 obj["aet"] = ["ate","eat","tea"]）；
待上述遍历结束，再遍历 obj，将 obj 的每一个值，push 到 arr 中。
const groupAnagrams = function (strs) {const obj = {};const arr = [];// 遍历数组for (let i = 0; i < strs.length; i++) {// 将每个字母异位词进行排序，并将排序后的字符串作为 keyconst 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;};
复杂度分析
时间复杂度：
外层 strs for 循环为 ，里面根据字符数据进行排序，查资料得排序时间复杂度为 ，k 为字符串长度最大值，即整个时间复杂度为 。
空间复杂度：
代码运行时创建了 obj 对象用于存储 strs 中的字符串，空间与 strs 长度与字符串长度成正比关系，所以空间复杂度为 。
思路
我们先遍历数组，每次都创建一个长度为 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;}// 将每个数组转化的字符串作为 keyconst 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;};
复杂度分析
时间复杂度：
外层 strs for 循环为 ，内层为对字符串进行 for 循环，时间复杂度为 ，k 为字符串长度最大值，即整个时间复杂度为 。
空间复杂度：
代码运行时创建了 obj 对象用于存储 strs 中的字符串，空间与 strs 长度与字符串长度成正比关系，所以空间复杂度为 。
给定一个包含 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;};
复杂度分析
时间复杂度：
解法虽然简单，套三重循环，时间复杂度高。
空间复杂度：
额外申请了uniqueMap的空间，复杂度为
思路
首先对数组进行排序，便于在插入的时候去重，进行双指针遍历时，遇到重复的数就可以很方便得跳过。
详解
先将数组排序，令左指针，右指针，当时，进行循环
当 时，将三个数插入数组，同时判断 和 是否重复，去重复解之后，同时将 和 移到下一个位置
若 小于 0，说明 太小， 需要右移，
若 大于 0，说明 太大， 需要左移,
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;};
复杂度分析
时间复杂度：
数组遍历 ，双指针遍历 ，因此复杂度为 为
空间复杂度：
指针使用常数大小的额外空间
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例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;};
复杂度分析
时间复杂度：
这样子需要从前向后遍历一遍长度为 的字符串，需要进行 次字符是否重复的比较。
空间复杂度：
在计算比较过程中，数组最长有可能存放 个不重复字符串。
从前到后遍历字符串，维护一个string，记录着不重复字符子串。 每当遇到重复的字符时候，找到string中重复的字符，并截断。 循环往复直到遍历最后一个字符.
思路
记录当前正在遍历的不重复字串的子集 string ， 在遍历过程中不断地添加不重复字符，遇到重复字符则截断 string 达到 string 内补字符不重复的条件。
详解
初始化一个 string 和最大值，
从前向后遍历字符串，
如果该字符不在 string 中，则添加字符到 string 中，并记录下最大值。
否则就截断字符串，如此循环直到结束。
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;};
复杂度分析
时间复杂度：
我们只遍历了包含有 个元素的字符串一次。
空间复杂度：
所需的额外空间取决于子串的长度，子串始终小于等于传入字符串的长度，该子串最多需要存储 个元素。
给定一个 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]]
进阶
一个直接的解决方案是使用 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
注意事项
注意边遍历边修改原数组，以免未遍历元素受 0 值的影响。
思路
申请额外空间去记录需要置为 0 的行号和列号
详解
申请 的额外空间，声明两个数组，所占空间最大值分别为 ，，分别存放水平方向、垂直方向应该重置为零的元素下标
从上到下，从左到右依次遍历原数组，记录元素为 0 的横坐标与纵坐标到提前声明的两个需置零的数组
待遍历结束后，再次遍历原数组，按照两个需置零的数组把元素置为零。
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;}}};
时间复杂度：
算法包括两个遍历，运行次数为是 ，所以时间复杂度是
空间复杂度：
额外空间包括若干个常量和两个长度分别为 ，的数组
思路
我们不能再额外创建数组来记录 0 的位置，从原数组本身找突破点，用原数组的第一行和第一列记录该行或该列需不需要置零，再根据首行首列的标识对元素置零
参考图
详解
首先从左到右，从上到下遍历数组中每一个元素（列遍历从第二列开始），若该元素为 0，则同时设置改行首列元素、首行该列元素为 0，若首列存在为 0 元素，则设置标识，意为首列元素会被全部置零，此目的是区分行元素与首列元素置零的标识，
然后，从右到左，从下到上遍历数组，若首行该列或该行首列元素为 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;}}};
复杂度分析：
时间复杂度：
算法包括两个遍历，运行次数都是 ，所以时间复杂度是
空间复杂度：
额外空间包括若干个常量，与 、大小无关
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 ，空间复杂度为 。
示例 1:
输入: [1, 2, 3, 4, 5];输出: true;
示例 2:
输入: [5, 4, 3, 2, 1];输出: false;
思路
使用 one 和 two 两个数。保证 one 小于 two，若遍历到一个数大于 two，则满足3个数递增。返回true
设置两个变量，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;};
复杂度分析
时间复杂度：，遍历了1次含个元素的空间
空间复杂度：，遍历过程没有用到新的空间存储数据
思路
循环遍历数组，不断更新数组内出现的最小值与最大值，如果出现的一个大于最大值的数，则表示存在长度为 3 的递增子序列。
详解
若目标数组 nums 存在递增的三元子序列，设这三个数为 a1,a2,a3,则
a3>a2>a1。可以先定义两个变量 small, big (samll < big) 分别用于存放最小的两个数字，在js中使用
Number.MAX_SAFE_INTEGER常量表示最大的安全整数（maxinum safe integer)（2^53 - 1）。遍历数组，实时捕获当前最小的两个数，同时判断在这两个数后方是否存在一个数字
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;};
复杂度分析
时间复杂度：
遍历了 1 次含 个元素的空间
空间复杂度：
遍历过程没有用到新的空间存储数据
