【算法刷题】leetcode hot 100 哈希篇

---

1. 两数之和

1. leetcode：https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-100-liked
2. 暴力解决：

    public int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = 0; j < nums.length; j++) {if (j == i) {continue;}if (nums[j] == target - nums[i]) {return new int[]{i, j};}}}return new int[]{};}

3. 哈希解决：

   public int[] twoSum(int[] nums, int target) {// <Value, Index>Map<Integer, Integer> map = new HashMap<>();for (int i = 0;i < nums.length; i++) {int complete = target - nums[i];if (map.containsKey(complete)) {return new int[]{map.get(complete), i};}map.put(nums[i], i);}return new int[]{};}

---

49. 字母异位词分组

1. leetcode：https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-100-liked
2. 使用排序法：

思路：
（1）. 对每个字符串进行排序。
（2）. 使用排序后的字符串作为哈希表的键，将相同的字母异位词放在同一组中。

    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 key = new String(chars);if (!map.containsKey(key)){map.put(key, new ArrayList<>());}map.get(key).add(str);}return new ArrayList<>(map.values());}

3. 使用字符计数法

思路：
（1）. 对于每个字符串，统计其字符出现的频次，使用一个数组或哈希表表示这个频次。
（2）. 将频次数组或频次哈希表作为哈希表的键，将字母异位词加入同一组。

    public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {int[] counts = new int[26];for (char c : str.toCharArray()) {counts[c - 'a']++;}String key = Arrays.toString(counts);if (!map.containsKey(key)) {map.put(key, new ArrayList<>());}map.get(key).add(str);}return new ArrayList<>(map.values());}

---

128. 最长连续序列

1. leetcode：https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

2. 解法：
   通过判断一个数字是否是序列的起点来高效检查最长连续序列。

    public int longestConsecutive(int[] nums) {if (nums == null || nums.length == 0) {return 0;}// 将所有数字加入哈希集合HashSet<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);}int max = 0;// 遍历集合for (int num : set) {// 仅从序列的起点开始扩展if (!set.contains(num - 1)) {int currentNum = num;int currentStreak = 1;// 向后扩展序列while (set.contains(currentNum + 1)) {currentNum++;currentStreak++;}// 更新最大长度max = Math.max(max, currentStreak);}}return max;}

---

总结

在算法题中，使用哈希表（HashMap）是一种非常高效的工具，特别适用于解决需要快速查找、配对、或分组的问题。

1. 快速查找：

• 需要在数组或集合中快速查找某个元素是否存在。
• 示例：两数之和。

2. 分组：

• 根据某种规则，将元素分为若干组，键是规则标识，值是元素列表。
• 示例：字母异位词分组。

3. 记录频率或状态：

• 统计元素出现的频率，或跟踪元素是否被访问。

4. 配对与索引存储：

• 存储某个值对应的另一部分信息，比如索引或其余条件。

解题步骤：

• 明确题意：
  • 确定是否需要频繁查找或分组操作。
• 确定哈希表结构：
  • Key：作为分组或查找的标识（例如目标值的差值、排序后的字符串）。
  • Value：存储关联的值（例如索引、元素列表等）。
• 遍历与处理：
  • 遍历数组，根据逻辑将元素存入或从哈希表中取出。
• 返回结果：
  • 按题目要求返回处理后的结果。

---