力扣 Hot 100 题解 （js版）更新ing

🚩哈希表

✅ 1. 两数之和

Code：

暴力法

复杂度分析：

• 时间复杂度：$\ast O(N^2)\ast$，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：O(1)。

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var twoSum = function(nums, target) {let len = nums.lengthfor (let i = 0; i < len; i++) {for (let j = i + 1; j < len; j++) {if (nums[i] + nums[j] === target) {return [i, j]}}}
};

哈希表

复杂度分析：

• 时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
• 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

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

---

---

---

✅ 49. 字母异位词分组

题目 “字母异位词分组” 的目标是将一组字符串按照字母异位词（即字符串由相同的字母组成，字母顺序不同）分组。

我们可以通过以下思路解决：

思路：

1. 特征值：排序法
   • 字母异位词具有一个共同特点：它们的字母排序后会得到相同的结果。
   • 例如："eat" 和 "tea" 排序后都是 "aet"。
   • 将每个字符串的排序结果作为键，将具有相同排序结果的字符串分到同一组。
2. 数据结构：
   • 使用一个哈希表（Map），键是排序后的字符串，值是一个数组，存储具有相同特征值的字符串。
3. 步骤：
   • 遍历字符串数组，对每个字符串排序。
   • 将排序后的字符串作为键存入哈希表，值是对应的字符串数组。
   • 遍历完成后，哈希表的值即为分组结果。

Code:

复杂度分析：

1. 时间复杂度：
   • 对每个字符串进行排序的时间复杂度为 $O(k\log k)$，其中 $k$ 是字符串的平均长度。
   • 遍历数组的时间复杂度为 $O(n)$，其中 $n$ 是字符串数组的长度。
   • 总时间复杂度为 $O(n\cdot k\log k)$。
2. 空间复杂度：
   • 使用了一个哈希表来存储分组结果，空间复杂度为 $O(n\cdot k)$，其中 $n$ 是字符串数组的长度，$k$ 是字符串的平均长度。

/*** 字母异位词分组* @param {string[]} strs* @return {string[][]}*/
function groupAnagrams(strs) {const map = new Map(); // 创建一个哈希表for (const str of strs) {// 对字符串排序后作为特征值const sortedStr = str.split('').sort().join('');// 如果哈希表中没有该特征值，则初始化为一个数组if (!map.has(sortedStr)) {map.set(sortedStr, []);}// 将字符串加入对应的组map.get(sortedStr).push(str);}// 返回所有分组的数组return Array.from(map.values());
}// 测试用例
const strs = ["eat", "tea", "tan", "ate", "nat", "bat"];
console.log(groupAnagrams(strs));

运行结果：

对于输入 ["eat", "tea", "tan", "ate", "nat", "bat"]，输出为：

[["eat", "tea", "ate"],["tan", "nat"],["bat"]
]

扩展（优化排序法）：

如果希望优化排序的时间，可以考虑使用字符计数代替排序，形成一个唯一的特征值，例如：

• 对于 "eat"，记录字符频率为 "1#1#1#0#0#..."，用这种方式构建键。

---

---

---

✅ 128. 最长连续序列

题目 128：最长连续序列

给定一个未排序的整数数组，找出其中最长连续元素序列的长度。要求算法的时间复杂度为 $O(n)$。

---

解题思路：

要实现 $O(n)$ 的时间复杂度，我们可以利用哈希表（Set）来快速检查连续的数字是否存在：

1. 将所有数字存入哈希表（Set）：
   • 使用哈希表存储数组中的所有数字，便于快速查找某个数字是否存在。
2. 遍历数组，寻找序列的起点：
   • 对每个数字 num，检查是否存在 num - 1。
   • 如果不存在 num - 1，说明 num 是一个序列的起点。
   • 从 num 开始，依次检查 num + 1 是否存在，计算序列的长度。
3. 记录最长序列的长度：
   • 在遍历过程中，更新最长序列长度。

---

Code：

复杂度分析

1. 时间复杂度：
   • 将数组转换为哈希表的时间复杂度是 $O(n)$。
   • 遍历每个数字，并检查哈希表的操作为 $O(1)$。
   • 每个序列中的数字最多只被遍历一次，因此整体时间复杂度为 $O(n)$。
2. 空间复杂度：
   • 需要额外的哈希表存储所有数字，空间复杂度为 $O(n)$。

/*** 最长连续序列* @param {number[]} nums* @return {number}*/
function longestConsecutive(nums) {// 将数组转化为哈希集合const numSet = new Set(nums);let maxLength = 0;// 遍历数组中的每个数字for (const num of numSet) {// 如果 num 是序列的起点（num - 1 不存在）if (!numSet.has(num - 1)) {let currentNum = num;let currentLength = 1;// 找到当前序列的长度while (numSet.has(currentNum + 1)) {currentNum += 1;currentLength += 1;}// 更新最大长度maxLength = Math.max(maxLength, currentLength);}}return maxLength;
}// 测试用例
const nums = [100, 4, 200, 1, 3, 2];
console.log(longestConsecutive(nums)); // 输出: 4 (最长序列是 [1, 2, 3, 4])

---

---

---

🚩 双指针

✅ 283. 移动零

暴力法

复杂度分析：

• 时间复杂度：$O(n^2)$
• 空间复杂度：O(1)

这段代码的时间复杂度是 ( O(n^2) )，这是由于 splice 操作引起的。为了优化，应该避免在循环中频繁操作数组结构，比如可以采用额外的空间存储非零元素，最后再重组数组，这样可以将时间复杂度降低到 ( O(n) )。

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var moveZeroes = function(nums) {let len = nums.lengthfor (let i = 0; i < len; i++) {if (nums[i] === 0) {nums.splice(i, 1)nums.push(0)i--len--}}
};

---

指针法

思路：

• 从左到右遍历 nums[i]。

同时维护另一个下标 index（初始值为 0），并保证下标区间 [ index, i−1] 都是空位，且 index 指向最左边的空位。每次遇到 nums[i] =0 的情况，就把 nums[i] 移动到最左边的空位上，也就是交换 nums[i] 和 nums[index]。交换后把 index和 i 都加一，从而使【[index,i−1] 都是空位】这一性质仍然成立。如果 nums[i]=0，无需交换，只把 i 加一。

示例 1 的 nums=[0,1,0,3,12]，计算过程如下（下划线表示交换的两个数）：

Code：

/*** @param {number[]} nums* @return {void} Do not return anything, modify nums in-place instead.*/
var moveZeroes = function(nums) {let index = 0let len = nums.lengthfor (let i = 0; i < len; i++) {if (nums[i] !== 0) {// 交换非0元素到前面[nums[index], nums[i]] = [nums[i], nums[index]]index++}}
};

---

---

✅ 11. 盛最多水的容器

问题描述：

给定一个数组 height，其中 height[i] 代表一个点的高度，表示横坐标为 i 处的高度。找出两个线段，使得它们和 x 轴所围成的容器能够容纳最多的水。返回这个容器能够容纳的水的最大值。

例子：

输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 最终盛水容器的高度为 7（索引 1 和 8 之间的最小高度），宽度为 8（索引 8 减去索引 1），所以最大水量为 7 * 8 = 49。

题目分析：

这是一个经典的 容器问题，要求找出两个垂直的线段，它们与 x 轴围成的容器能够容纳最多的水。显然，容器的面积是由这两个线段之间的距离（宽度）和两条线段的高度中的较小值决定的。

• 宽度：由两个指针之间的距离决定，假设两个指针分别指向数组的索引 left 和 right，那么宽度为 right - left。
• 高度：由较短的线段的高度决定，即 Math.min(height[left], height[right])。

解题思路：

我们可以使用 双指针 方法来解决这个问题，以下是详细的步骤：

1. 初始化：设置两个指针，left 指向数组的第一个元素，right 指向数组的最后一个元素。
2. 计算当前容器的水量：每次计算当前两个指针之间容器的水量，即 Math.min(height[left], height[right]) * (right - left)。
3. 更新最大水量：记录当前最大水量，并更新最大值。
4. 移动指针：为了找到可能更大的水量，每次移动指向较小高度的指针。
   • 如果 height[left] < height[right]，说明移动左指针可能会找到更大的水量，因为左指针所在的高度较小。
   • 否则，移动右指针。

Code：

复杂度分析：

• 时间复杂度： $O(n)$ ，我们使用双指针，每次移动一个指针，最多遍历一次数组，因此时间复杂度为 $O(n)$ ，其中 n 是数组的长度。
• 空间复杂度：$O(1)$ ，我们只使用了常量级的额外空间。

/*** @param {number[]} height* @return {number}*/
var maxArea = function(height) {let left = 0;          // 初始化左指针let right = height.length - 1;  // 初始化右指针let maxArea = 0;       // 记录最大水量while (left < right) {// 计算当前容器的水量const currentArea = Math.min(height[left], height[right]) * (right - left);// 更新最大水量maxArea = Math.max(maxArea, currentArea);// 移动指针，移动较小的那个指针if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
};

代码解释：

1. 初始化：
   • left = 0：指向数组的第一个元素。
   • right = height.length - 1：指向数组的最后一个元素。
   • maxArea = 0：记录当前的最大水量。
2. 循环：
   • 在 left 小于 right 的情况下，计算当前容器的水量。
   • currentArea = Math.min(height[left], height[right]) * (right - left)：计算当前水量，Math.min(height[left], height[right]) 是容器的高度，right - left 是容器的宽度。
   • 使用 Math.max(maxArea, currentArea) 更新最大水量。
3. 移动指针：
   • 如果 height[left] < height[right]，移动左指针 left++，否则移动右指针 right--。
   • 移动指针的目的是寻找可能的更高的容器边界，以增加水量。
4. 返回最大水量：最终，返回 maxArea，即找到的最大容器水量。
   总结：

• 使用 双指针 方法能高效地解决这个问题，通过每次移动较小的指针来尝试找到更大的水容积。
• 时间复杂度为 ( O(n) )，空间复杂度为 ( O(1) )，这使得这个方法非常高效。

---

---

✅ 15. 三数之和

问题描述：

给定一个包含 n 个整数的数组 nums，判断数组中是否存在三个元素 nums[i]、nums[j]、nums[k]（满足 i != j 且 i != k 且 j != k），使得它们的和为零。如果存在，返回所有不重复的三元组。

示例 1：

输入: nums = [-1, 0, 1, 2, -1, -4]
输出: [[-1, -1, 2], [-1, 0, 1]]

示例 2：

输入: nums = []
输出: []

示例 3：

输入: nums = [0, 0, 0]
输出: [[0, 0, 0]]

解题思路：

这个问题通常是使用 排序 和 双指针 来优化寻找三元组的过程。其基本思路如下：

1. 排序数组：首先，我们将输入数组进行排序。这是为了便于利用双指针方法减少不必要的计算。
2. 固定一个元素：通过循环遍历数组，固定一个元素 nums[i]，然后在剩余的部分使用双指针查找其余两个元素，使得三者和为零。
3. 双指针法：对于每次固定的 nums[i]，设置两个指针 left 和 right，分别指向当前元素后面的第一个元素和数组的最后一个元素。通过移动 left 和 right 来找到符合条件的两个数。
4. 去重：由于数组可能包含重复元素，我们需要避免重复的三元组，可以通过跳过重复元素来去重。

Code:

复杂度分析：

• 时间复杂度：
  • 排序时间复杂度为 ($O(n\log n)$。
  • 遍历每个元素时，内部的双指针查找两个数的时间复杂度为 ($O(n)$。
  • 因此，总的时间复杂度是 $O(n^2$)。
• 空间复杂度：
  • 由于使用了一个额外的数组来存储结果，空间复杂度是 ($O(n)$，其中 $n$ 是数组的长度。

/*** @param {number[]} nums* @return {number[][]}*/
var threeSum = function(nums) {let result = [];// 1. 排序数组nums.sort((a, b) => a - b);// 2. 遍历数组，固定一个元素，利用双指针查找另外两个数for (let i = 0; i < nums.length - 2; i++) {// 2.1 跳过重复的元素if (i > 0 && nums[i] === nums[i - 1]) {continue;}let left = i + 1, right = nums.length - 1;while (left < right) {let sum = nums[i] + nums[left] + nums[right];if (sum === 0) {// 找到符合条件的三元组result.push([nums[i], nums[left], nums[right]]);// 跳过重复的元素while (left < right && nums[left] === nums[left + 1]) left++;while (left < right && nums[right] === nums[right - 1]) right--;// 移动指针left++;right--;} else if (sum < 0) {// 和小于 0，说明需要增大 sum，左指针右移left++;} else {// 和大于 0，说明需要减小 sum，右指针左移right--;}}}return result;
};

代码解析：

1. 排序数组：

   nums.sort((a, b) => a - b);

   排序数组的目的是为了后续使用双指针可以更容易地处理和为零的情况。如果没有排序，我们就不能有效地利用双指针来加速查找。

2. 遍历数组并固定一个元素：

   for (let i = 0; i < nums.length - 2; i++) {if (i > 0 && nums[i] === nums[i - 1]) {continue;}

   我们遍历数组中的每个元素作为固定的第一个元素 nums[i]。在遍历过程中，如果遇到重复的元素，就跳过，以避免重复计算相同的三元组。

3. 双指针查找其余两个元素：

   let left = i + 1, right = nums.length - 1;
   while (left < right) {let sum = nums[i] + nums[left] + nums[right];

   对于每个固定的元素 nums[i]，我们通过 left 和 right 两个指针来查找剩下的两个元素。初始时，left 指向 i+1，right 指向数组的最后一个元素。

4. 判断三元组和的大小并调整指针：

   • 如果三者和 sum 为 0，说明找到了符合条件的三元组，将其加入结果数组。
   • 如果 sum < 0，说明和太小，需要增大和，因此移动 left 指针。
   • 如果 sum > 0，说明和太大，需要减小和，因此移动 right 指针。

5. 去重处理：
   在找到一个三元组后，我们需要跳过重复的元素，以避免结果中包含重复的三元组：

   while (left < right && nums[left] === nums[left + 1]) left++;
   while (left < right && nums[right] === nums[right - 1]) right--;

6. 返回结果：
   最终，我们返回所有符合条件的三元组。

总结：

• 使用排序和双指针方法是解决 三数之和 问题的常见方法。
• 排序可以帮助我们减少不必要的计算，使得时间复杂度从 (O(n^3)) 降低到 (O(n^2))。
• 通过跳过重复元素，可以避免结果中出现重复的三元组。