哈希算法练习

哈希表（Hash Table）利用哈希函数将键（Key）映射到桶（Bucket）中，从而实现 O(1) 的平均查找时间。它是解决查找、频率统计和去重问题的常用利器。

1. 两数之和 (Two Sum)

题目描述

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

解题思路

利用哈希表存储已经遍历过的数值和对应的下标。当遍历到当前数 nums[i] 时，检查哈希表中是否存在 target - nums[i]，若存在则返回对应下标。

Java 代码实现

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);
        }
        return new int[]{-1, -1};
    }
}

---

49. 字母异位词分组 (Group Anagrams)

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。 字母异位词是由重新排列源单词的所有字母得到的一个新单词。

解题思路

字母异位词排序后的字符串一定相同。因此可以遍历数组，将每个单词单词排序后的形式作为哈希表的 Key，对应的列表作为内容进行聚合。

Java 代码实现

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 key = new String(chars);
            map.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }
}

---

128. 最长连续序列 (Longest Consecutive Sequence)

题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求算法的时间复杂度为 O(n)。

解题思路

使用 HashSet 存储所有数字。遍历数组，对于每个数 x，如果 x-1 不在 Set 中，说明 x 是一个连续序列的起点。然后从 x 开始不断递归查找 x+1, x+2...，更新最大长度。

Java 代码实现

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) set.add(num);
        int maxLen = 0;
        for (int num : set) {
            if (!set.contains(num - 1)) {
                int currNum = num;
                int currLen = 1;
                while (set.contains(currNum + 1)) {
                    currNum++;
                    currLen++;
                }
                maxLen = Math.max(maxLen, currLen);
            }
        }
        return maxLen;
    }
}