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

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