【LeetCode 热题 100】（一）哈希

1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        // 1.声明一个hashmap {nums[i], i}
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < length; i++) {
            int second = target - nums[i];
            if(map.containsKey(second)){
                int j = map.get(second);
                return new int[]{i,j};
            }
            map.put(nums[i],i);
        }
        return new int[]{};     
    }
}

这段代码实现了在整数数组 nums 中找到两个数，使它们的和等于给定的目标值 target，并返回这两个数的索引。其解题思路基于 哈希表优化查找效率，具体步骤如下：

解题思路描述：

1. 初始化哈希表：

   • 创建一个 HashMap<Integer, Integer>，键（Key）存储数组元素的值，值（Value）存储该元素的索引。
   • 目标：通过值快速查找对应的索引。

2. 遍历数组：

   • 对每个元素 nums[i]，计算其配对值 second = target - nums[i]（即满足 nums[i] + second = target 的值）。

3. 检查配对值是否存在：

   • 在哈希表中查找 second：
     • 若存在：说明 second 是之前遍历过的某个元素的值，其索引 j = map.get(second) 与当前索引 i 即为解。
     • 直接返回 {i, j}（顺序为 i 在后，j 在前）。
   • 若不存在：将当前值 nums[i] 及其索引 i 存入哈希表，继续遍历。

4. 遍历结束处理：

   • 若循环结束未找到解，返回空数组 {}（题目保证有解，此步为语法完整性）。

关键点分析：

• 高效查找：哈希表在平均 O(1) 时间内完成 containsKey 和 get 操作，将整体时间复杂度优化至 O(n)。
• 避免重复使用：先检查配对值再存入当前值，确保不会将同一元素使用两次（例如 target = 4, nums[i] = 2 时，先检查 2 是否已存在，再存入当前 2）。
• 顺序无关：返回索引顺序取决于遍历顺序（j 为哈希表中存储的较早索引，i 为当前索引）。

示例说明：

• 输入：nums = [3, 2, 4], target = 6
• 步骤：
  1. i=0：nums[0]=3 → second=3（6-3），哈希表为空 → 存入 (3,0)。
  2. i=1：nums[1]=2 → second=4（6-2），哈希表无 4 → 存入 (2,1)。
  3. i=2：nums[2]=4 → second=2（6-4），哈希表存在 2（索引 j=1）→ 返回 {2, 1}。

复杂度：

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(n)，哈希表存储最多 n 个元素。

此方法以空间换时间，高效解决了“两数之和”问题。

49. 字母异位词分组

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
           HashMap<String, List<String>> map = new HashMap<>();


        for (String item : strs) {
            // 1. 声明字母数组
            int[] count1 = new int[26];
            // 2. 将字母转换位对应的ascii 存储到数组下标
            for (int i = 0; i < item.length(); i++) {
                char c = item.charAt(i);
                int poi = c - 'a';
                count1[poi] = count1[poi] + 1;
            }
            // 3. 在将数组下标转换位字母
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if(count1[i] != 0){
                    sb.append((char) (i + 'a'));
                    sb.append(count1[i]);
                }
            }
            // 4. 判断map中键中是否包含
            String key = sb.toString();
            List<String> list1 = map.getOrDefault(key, new LinkedList<>());
            list1.add(item);
            map.put(key, list1);
        }
        List<List<String>> list = new LinkedList<>(map.values());

        return list;
        
    }
}

解题思路描述

这段代码实现了将一组字符串按字母异位词（Anagram） 分组的功能。字母异位词指字母相同但排列不同的字符串（如 “eat” 和 “tea”）。核心思路是 为每个字符串生成唯一的特征编码作为哈希表的键，具体步骤如下：

1. 初始化哈希表

HashMap<String, List<String>> map = new HashMap<>();

• 键（Key）：字符串的特征编码（字母出现频次的唯一标识）
• 值（Value）：所有具有相同特征编码的字符串组成的列表

2. 遍历所有字符串

对每个字符串 item 执行以下操作：

for (String item : strs) {
    // 步骤2.1 ~ 2.4
}

2.1 统计字母频次

int[] count1 = new int[26];
for (int i = 0; i < item.length(); i++) {
    char c = item.charAt(i);
    int poi = c - 'a';  // 将字母映射到 0-25 的索引
    count1[poi]++;      // 对应字母计数+1
}

• 创建长度 26 的数组（对应 a-z）
• 遍历字符串中的每个字符，在数组中记录其出现次数

2.2 生成特征编码（关键步骤）

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
    if(count1[i] != 0){
        sb.append((char) (i + 'a')); // 添加字母
        sb.append(count1[i]);        // 添加出现次数
    }
}
String key = sb.toString();

• 将统计数组转换为唯一字符串标识（如 “a2b1” 表示 a 出现 2 次，b 出现 1 次）
• 为什么有效：
  字母异位词的统计结果相同 → 生成的 key 相同
  非字母异位词统计结果不同 → 生成的 key 不同

2.3 分组存储到哈希表

List<String> list1 = map.getOrDefault(key, new LinkedList<>());
list1.add(item);
map.put(key, list1);

• 若 key 不存在：创建新列表
• 若 key 已存在：获取现有列表
• 将当前字符串添加到对应列表

3. 返回分组结果

return new LinkedList<>(map.values());

• 哈希表的 values() 就是所有分组结果
• 直接转换为列表返回（每个子列表是一组字母异位词）

关键优势

1. 精确分组
   通过字母频次统计确保只有字母异位词共享同一 key
2. 避免排序
   相比对每个字符串排序（O(klogk)），统计频次只需 O(k)（k 为字符串长度）
3. 哈希表高效操作
   插入和查询操作均摊时间复杂度 O(1)

复杂度分析

• 时间复杂度：O(n × k)
  • n：字符串数组长度
  • k：最长字符串长度（每个字符串需遍历统计）
• 空间复杂度：O(n × k)
  • 哈希表存储所有字符串的特征编码和分组列表

示例说明

输入：["eat", "tea", "tan"]
处理过程：

1. “eat” → 统计：a1,e1,t1 → 特征码：“a1e1t1”
2. “tea” → 统计：a1,e1,t1 → 特征码：“a1e1t1” → 与 “eat” 同组
3. “tan” → 统计：a1,n1,t1 → 特征码：“a1n1t1” → 新分组
   输出：[ ["eat","tea"], ["tan"] ]

128. 最长连续序列

class Solution {
    public int longestConsecutive(int[] nums) {
        int max_long = 0;

        Set<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int num : hashSet) {
            // 1.判断当前的前一位是否在集合中
            if(!hashSet.contains(num - 1)){
                int curr_num = num;
                int current_long = 1;
                // 2.全局最大的子序列和当前子序列长度
                while (hashSet.contains(curr_num + 1)){
                    curr_num = curr_num + 1;
                    current_long = current_long + 1;

                }
                max_long = Math.max(current_long, max_long);
            }
        }
        return max_long;

    }
}

解题思路描述

这段代码实现了在未排序整数数组中寻找最长连续序列长度的功能。核心思路是 利用哈希集合实现高效查找，并通过 跳过非连续序列起点 避免重复计算，具体步骤如下：

1. 初始化哈希集合

Set<Integer> hashSet = new HashSet<>();
for (int num : nums) {
    hashSet.add(num);
}

• 将所有数字存入哈希集合，实现 O(1) 时间复杂度的查找
• 自动去除重复元素，避免冗余处理

2. 寻找连续序列起点

for (int num : hashSet) {
    if(!hashSet.contains(num - 1)) { // 关键判断
        // 处理连续序列...
    }
}

• 核心思想：只从连续序列的起点开始计算
• 判断条件：num-1 不存在于集合中 → 说明 num 是某个连续序列的最小值（起点）
• 为什么有效：
  若非起点（如 num=3 时 num-1=2 存在），说明它属于某个更长序列的中间部分，后续会被起点覆盖计算

3. 扩展连续序列

int curr_num = num;
int current_long = 1;
while (hashSet.contains(curr_num + 1)) {
    curr_num++;          // 移动到下一个数字
    current_long++;      // 序列长度+1
}

• 从起点 num 开始向后扩展序列（num, num+1, num+2,...）
• 每找到一个连续后继数字：
  • 移动当前数字指针 curr_num
  • 增加当前序列长度 current_long
• 当 curr_num+1 不存在时，序列终止

4. 更新全局最大值

max_long = Math.max(current_long, max_long);

• 比较当前序列长度与历史最大值
• 始终保持 max_long 为遍历过程中的最大序列长度

5. 返回结果

return max_long;

• 返回全局最长连续序列长度

关键优势

1. 高效去重
   使用 HashSet 自动处理重复元素，避免无效计算
2. 起点优化策略
   仅从序列起点开始扩展，确保每个连续序列只计算一次
3. 时间复杂度优化
   看似嵌套循环，实际每个元素最多被访问两次（集合构建+序列扩展），整体 O(n) 复杂度

复杂度分析

• 时间复杂度：O(n)
  • 集合构建：O(n)
  • 序列扩展：每个元素最多被内层循环访问一次
• 空间复杂度：O(n)
  • 哈希集合存储所有元素

示例说明

输入：[100, 4, 200, 1, 3, 2]
处理过程：

1. 构建集合：{1, 2, 3, 4, 100, 200}
2. 遍历元素：
   • 100：99不存在 → 起点 → 向后扩展：101不存在 → 长度=1
   • 4：3存在 → 非起点 → 跳过
   • 200：199不存在 → 起点 → 向后扩展：201不存在 → 长度=1
   • 1：0不存在 → 起点 → 向后扩展：2,3,4存在 → 5不存在 → 长度=4
   • 2和3：非起点 → 跳过
3. 返回最大值：4（序列 1→2→3→4）