文章目录
在力扣（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）
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）
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）
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;
}
}
5. 复杂度分析
- 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，对于每个元素，哈希表的查找和插入操作都是 O(1) 的。
- 空间复杂度 ：O(n)，需要使用哈希表存储数组中的元素及其连续序列长度。
以上就是力扣热题 100 中与哈希相关的三道题的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。
