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

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.length
    for (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 []
};

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

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

思路：

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#..."，用这种方式构建键。