梦开始的地方：力扣热题100哈希表

文章目录

• 前言
• 一、哈希表是什么
• 二、力扣解题常见的三种哈希结构（java版本）
• • 1.数组
  • 2.set （集合）
  • 3.map（映射）
• 总结

前言

在刷力扣100题的征程中，我从哈希相关题目入手，一路探索，收获颇丰。如今，想将自己在这一过程中的思路与感悟进行一番总结，既为记录成长，也希望能给同样在算法之路上前行的朋友们提供一些参考。

一、哈希表是什么

优化后的表格内容如下：

哈希表在实际应用中，常被用于快速判定一个元素是否存在于集合之中，其高效性大幅提升了数据处理的效率与便捷性。

二、力扣解题常见的三种哈希结构（java版本）

1.数组

• 力扣题目链接：有效的字母异位词
• 分析 ：为何选用数组？在处理这道题时，我们需要对每个字符串进行遍历，并将相关信息记录下来，以便后续的分析与查找。由于题目涉及的字母仅有26个，属于有限且固定的范围，使用数组能够高效地对字母出现的频次进行统计与管理 。
• 解题

    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()){
            return false;
        }
        int[] temp=new int[26];
        for(int i=0;i<s.length();i++){
            temp[s.charAt(i)-'a']++;
        }
        for(int j=0;j<t.length();j++){
            temp[t.charAt(j) - 'a']--;
            if (temp[t.charAt(j) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }

2.set （集合）

• 力扣题目链接：最长连续序列
• 分析 ：选择集合的原因在于，本题所涉及的数据量可能较大，集合的特性使其能够高效地存储和处理大量数据。同时，在判断连续序列时，利用集合可以方便地从最小值开始往前判断，简化了判断逻辑。
• 解题

    public static int longestConsecutive(int[] nums) {
        // 存储数据 去重
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        // 存储结果值
        int result = 0;
        for (Integer i : set) {
            // 检查是否是起点
            if (!set.contains(i - 1)) {
                int temp = i + 1;
                while (set.contains(temp)) {
                    temp++;
                }
                result = Math.max(result, temp - i);
            }
        }
        return result;
    }

3.map（映射）

• 力扣题目链接：两数之和
• 分析 ：本题选择map，主要是因为我们不仅需要记录数组中的值，还需要记录其对应的下标索引，以便在找到满足条件的两数时，能够准确地返回它们的下标。map的键值对结构恰好满足这一需求，通过将差值作为键，索引作为值存储，实现快速查找与匹配 。
• 解题

    public static int[] twoSum(int[] nums, int target) {
        // 定义一个hashMap存储数据 key：差值 value：索引
        HashMap<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[]{};
    }

• 力扣题目链接：字母异位词分组
• 分析 ：面对这道题，我们可以借助map强大的记录与分组能力。通过将排序后的字符串作为key，把具有相同字母组成（即字母异位词）的原始字符串作为value存储在map中，从而实现对字母异位词的高效分组。
• 解题

    public List<List<String>> groupAnagrams(String[] strs) {
        // 定义一个hashMap存储词
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            // 排序
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

总结

哈希表的卓越之处在于，在平均情况下，它能够以近乎常数时间（ O ( 1 ) O(1) O(1)）的速度执行插入、删除和查找操作，这一特性使其在众多算法场景中大放异彩。在后续的探索中，我会持续在这篇博客中更新更多关于哈希的力扣题目及解题思路，与大家一同在算法的海洋中遨游，不断提升自我。