力扣热题 100：哈希专题三道题详细解析(JAVA)

文章目录

- 一、两数之和
- - 1. 题目描述
  - 2. 示例
  - 3. 解题思路
  - 4. 代码实现（Java）
  - 5. 复杂度分析
- 二、字母异位词分组
- - 1. 题目描述
  - 2. 示例
  - 3. 解题思路
  - 4. 代码实现（Java）
  - 5. 复杂度分析
- 三、最长连续序列
- - 1. 题目描述
  - 2. 示例
  - 3. 解题思路
  - 4. 代码实现（Java）
  - 5. 复杂度分析

在力扣（LeetCode）平台上，热题 100 是许多开发者提升算法能力的必刷清单。今天，我们就来详细解析热题 100 中与哈希相关的三道题，帮助大家更好地理解解题思路和技巧。

一、两数之和

1. 题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

2. 示例

示例 1：

输入：nums = [2, 7, 11, 15], target = 9

输出：[0, 1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3, 2, 4], target = 6

输出：[1, 2]

解释：因为 nums[1] + nums[2] == 6 ，返回 [1, 2] 。

示例 3：

输入：nums = [3, 3], target = 6

输出：[0, 1]

解释：因为 nums[0] + nums[1] == 6 ，返回 [0, 1] 。

3. 解题思路

这道题是力扣上的经典入门题，主要考察哈希表的应用。我们可以使用哈希表来存储数组中的元素及其下标，然后遍历数组，对于每个元素，检查 target - nums[i] 是否在哈希表中存在。如果存在，则找到了答案。

4. 代码实现（Java）

java">import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

5. 复杂度分析

时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，对于每个元素，哈希表的查找和插入操作都是 O(1) 的。
空间复杂度 ：O(n)，需要使用哈希表存储数组中的元素及其下标。

二、字母异位词分组

1. 题目描述

给你一个字符串数组 strs，将 所有变位词 组合在一起。变位词是指字母相同，但排列不同的字符串。

注意：输出的顺序无关紧要。

2. 示例

示例 1：

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

“bat” 没有变位词。
“nat” 和 “tan” 是变位词。
“ate”, “eat” 和 “tea” 是变位词。

示例 2：

输入：strs = [""]

输出：[[""]]

解释：空字符串与自身是变位词。

示例 3：

输入：strs = ["a"]

输出：[["a"]]

解释：单个字符与自身是变位词。

3. 解题思路

这道题主要考察字符串的处理和哈希表的应用。我们可以将每个字符串排序后作为哈希表的键，将变位词作为哈希表的值。具体步骤如下：

创建一个哈希表，键为排序后的字符串，值为变位词列表。
遍历字符串数组，对每个字符串进行排序，然后将其添加到哈希表中。
最后，将哈希表的值（即变位词列表）作为结果返回。

4. 代码实现（Java）

java">import java.util.*;

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortedStr = new String(chars);
            if (!map.containsKey(sortedStr)) {
                map.put(sortedStr, new ArrayList<>());
            }
            map.get(sortedStr).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

5. 复杂度分析

时间复杂度 ：O(n * k log k)，其中 n 是字符串数组的长度，k 是字符串的最大长度。对于每个字符串，我们需要进行排序，排序的时间复杂度是 O(k log k)。
空间复杂度 ：O(n * k)，需要使用哈希表存储排序后的字符串和变位词列表。

三、最长连续序列

1. 题目描述

给定一个未排序的整数数组 nums，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

2. 示例

示例 1：

输入：nums = [100, 4, 200, 1, 3, 2]

输出：4

解释：最长连续序列是 [1, 2, 3, 4]，它的长度为 4。

示例 2：

输入：nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

输出：9

解释：最长连续序列是 [0, 1, 2, 3, 4, 5, 6, 7, 8]，它的长度为 9。

3. 解题思路

这道题主要考察哈希表的应用和连续序列的判断。我们可以使用哈希表来存储数组中的元素及其连续序列的长度。具体步骤如下：

创建一个哈希表，键为数组中的元素，值为该元素的连续序列长度。
遍历数组，对于每个元素：
- 如果该元素不在哈希表中，检查其相邻元素（num - 1 和 num + 1）是否在哈希表中。
- 如果相邻元素存在，更新当前元素的连续序列长度。
- 将当前元素及其连续序列长度存储到哈希表中。
最后，返回哈希表中的最大连续序列长度。

4. 代码实现（Java）

java">import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int longestConsecutive(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxLength = 0;
        for (int num : nums) {
            if (!map.containsKey(num)) {
                int left = map.getOrDefault(num - 1, 0);
                int right = map.getOrDefault(num + 1, 0);
                int length = left + right + 1;
                map.put(num, length);
                maxLength = Math.max(maxLength, length);
                if (left > 0) {
                    map.put(num - left, length);
                }
                if (right > 0) {
                    map.put(num + right, length);
                }
            }
        }
        return maxLength;
    }
}