【LeetCode Hot100 哈希】两数之和、字母异位词分组、最长连续序列

1. 两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target，在数组中找出两个数字，使它们的和为目标值 target。你需要返回这两个数字的下标。

注意:

• 你可以假设每个输入只会有一个答案，并且你可以按任意顺序返回答案。
• 不允许使用循环外的额外空间，且时间复杂度必须是 O(n)。

解题思路

为了高效地找到目标值 target 的两个数字，采用了哈希表来存储遍历过程中遇到的数字及其对应的索引。

步骤：

1. 初始化哈希表：
   我们使用一个哈希表 hashTable 来存储数组 nums 中每个数字及其对应的索引。哈希表的 key 为数字，value 为该数字在数组中的索引。

2. 遍历数组：
   我们遍历数组 nums，对于每个元素 nums[i]，检查哈希表中是否存在一个元素，使得 nums[i] 和该元素的和为 target。
   具体来说，我们检查哈希表中是否包含 target - nums[i]。如果存在，说明我们找到了两个数字，它们的和为 target，返回它们的下标。

3. 更新哈希表：
   如果当前数字 nums[i] 与之前的数字不能组成目标和，则将 nums[i] 和它的下标 i 存入哈希表，继续查找。

4. 返回结果：
   如果找到了满足条件的两个数字，就返回它们的下标；如果遍历结束后仍未找到，则返回空数组。

时间复杂度：

• 遍历一次数组，查找哈希表的操作时间复杂度为 O(1)，因此总的时间复杂度为 O(n)，其中 n 为数组的长度。

空间复杂度：

• 我们使用了一个哈希表来存储数组元素和其下标，哈希表的大小最多为数组的长度，因此空间复杂度为 O(n)。

代码实现

class Solution {public int[] twoSum(int[] nums, int target) {// 使用hashMap<Integer, Integer> hashTable = new HashMap<Integer, Integer>();for(int i = 0; i < nums.length; i++) {// 检查 target - nums[i] 是否在哈希表中if(hashTable.containsKey(target - nums[i])){return new int[]{hashTable.get(target - nums[i]), i};}// 将当前数字和其下标放入哈希表hashTable.put(nums[i], i);  }return new int[0];  // 如果没有找到，返回空数组}
}

2. 字母异位词分组

题目描述

给定一个字符串数组 strs，将字符串按字母异位词（Anagram）进行分组。字母异位词是指两个字符串中包含的字符完全相同，且字符的顺序不同。

例如，"eat"，"tea"，和 "ate" 是字母异位词。要求将这些字母异位词分到同一组中。

注意：

• 输入的字符串只包含小写字母。
• 需要将所有字母异位词按顺序返回。

解题思路

为了将字母异位词分组，我们可以利用字符串的字母排序特性：对于字母异位词，它们的排序结果是相同的。我们可以通过对字符串进行排序，将字母异位词映射到相同的键上，进而将它们分到同一组。

步骤：

1. 定义哈希表：
   使用一个哈希表 map，其键是排序后的字符串，值是一个包含所有字母异位词的列表。

2. 遍历字符串数组：
   对于每个字符串，将其转化为字符数组并进行排序，得到一个排序后的字符串。这个排序后的字符串作为哈希表的键。

3. 存入哈希表：
   查找哈希表中是否已经存在该键。如果存在，就将该字符串加入对应的列表；如果不存在，则在哈希表中创建一个新的列表并添加该字符串。

4. 返回结果：
   最后，哈希表中存储了所有的字母异位词分组，直接返回哈希表的所有值。

时间复杂度：

• 对于每个字符串，我们将其转化为字符数组并进行排序，排序的时间复杂度为 O(m log m)，其中 m 是字符串的长度。
• 遍历字符串数组的时间复杂度为 O(n)，其中 n 是字符串数组的长度。
• 因此，总的时间复杂度为 O(n * m log m)，其中 n 是字符串数组的长度，m 是字符串的平均长度。

空间复杂度：

• 哈希表存储了所有的字符串及其对应的字母异位词，因此空间复杂度为 O(n * m)，其中 n 是字符串数组的长度，m 是字符串的平均长度。

代码实现

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {// 将字符串转换为字符数组并排序char[] strArray = str.toCharArray();Arrays.sort(strArray);// 使用排序后的字符串作为键String key = new String(strArray); // 获取或创建该键的对应列表List<String> list =  map.getOrDefault(key, new ArrayList<String>());// 将当前字符串添加到列表中list.add(str);// 更新哈希表中的列表map.put(key, list);}// 返回哈希表的所有值，即字母异位词分组return new ArrayList<List<String>>(map.values());}
}

3. 最长连续序列

题目描述

给定一个无序的整数数组 nums，返回其中最长的连续元素序列的长度。

要求：你必须设计时间复杂度为 O(n) 的算法解决此问题。

解题思路

该题要求我们找到一个无序数组中的最长连续子序列。为了满足 O(n) 的时间复杂度，不能采用排序的方式，因为排序的时间复杂度为 O(n log n)。我们可以使用哈希集合（Set）来解决这个问题。

关键思路：

1. 使用哈希集合存储数组元素：
   将数组中的每个元素加入哈希集合中，能够在 O(1) 的时间内判断某个元素是否存在。

2. 只从连续序列的第一个元素开始搜索：
   遍历集合时，对于每个数字 num，我们只在 num-1 不在集合中的时候开始查找连续序列的长度。这样做可以避免重复计算（例如，当处理到序列中的中间元素时，已经遍历过它前面的元素）。

3. 扩展连续序列：
   对于每个有效的起点 num，我们尝试通过 num+1、num+2 等，找到该序列的最大长度。

4. 更新结果：
   每次找到一个新的序列，更新当前最长的连续序列的长度。

步骤：

1. 将数组元素加入哈希集合 set 中。
2. 遍历集合，对于每个元素 num：
   • 如果 num-1 不在集合中，说明 num 是某个连续序列的起点。
   • 向右扩展，检查 num+1 是否在集合中，直到不再连续为止。
   • 更新最长连续序列的长度。

时间复杂度：

• 将所有元素加入集合需要 O(n) 时间。
• 遍历数组时，每个元素最多会被处理一次，因此总的时间复杂度为 O(n)。

空间复杂度：

• 哈希集合存储了所有数组元素，因此空间复杂度为 O(n)。

代码实现

class Solution {public int longestConsecutive(int[] nums) {// 使用哈希集合存储数组元素Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int longest = 0;// 遍历数组中的每个元素for (int num : set) {// 如果 num-1 不在集合中，说明 num 是一个连续序列的起点if (!set.contains(num - 1)) {int currentNum = num;int currentLong = 1;// 向右扩展，寻找连续的数字while (set.contains(currentNum + 1)) {currentLong++;currentNum++;}// 更新最长连续子序列的长度longest = Math.max(longest, currentLong);}}return longest;}
}