java数据结构（哈希表—HashMap）含LeetCode例题讲解

1、HashMap的基本方法

1.1、基础方法（增删改查）

1.2、其他方法

2、HashMap的相关例题

2.1、题目介绍

2.2、解题

2.2.1、解题思路

2.2.2、解题图解

2.3、解题代码

1、HashMap的基本方法

HashMap 是一个散列表，它存储的内容是键值(key-value)映射。
HashMap 的 key 与 value 类型可以相同也可以不同，根据定义，不受限制。

1.1、基础方法（增删改查）

1.定义一个哈希表

HashMap<Integer, String> hashmap= new HashMap<Integer, String>();

2.添加键值对（key-value）（增）

hashmap.put(1, "string1"); // 执行完后hash表内为{1=string1}
hashmap.put(2, "string2"); // 执行完后hash表内为{1=string1, 2=string2}
hashmap.put(2, "string2"); // 执行完后hash表内为{1=string1, 2=string2, 3=string3}

3.根据key值访问value（查）

hashmap.get(1); // 返回string1
hashmap.get(2); // 返回string2
hashmap.get(3); // 返回string3

4.根据key值删除元素（删）

hashmap.remove(1); // 执行完后hash表内为{2=string2, 3=string3}
hashmap.remove(2); // 执行完后hash表内为{3=string3}
hashmap.remove(3); // 执行完后hash表内为{}
// 删除所有键值对
hashmap.clear();

5.替换 hashMap 中是指定的key对应的 value（改）

hashmap.replace(key,value); // 返回0

6.返回hashmap中键值对的数量

hashmap.size(); // 返回0

7.getOrDefault(Object key, V defaultValue)
此方法用于当Map集合中有这个key时，就使用这个key对应的value值，如果没有就使用默认值defaultValue；

hashmap.getOrDefault(key,defaultValue);

1.2、其他方法

1.检查hashMap中是否存在指定的key对应的映射关系

hashmap.containsKey(key);

2.检查hashMap中是否存在指定的value对应的映射关系

hashmap.containsValue(value);

3.hashmap是否为空

hashmap.isEmpty();

4.HashMap.values() 方法

hashmap.values(); // 返回所有Value值组成的集合

例如：
如果有HashMap: {1=Google, 2=Runoob, 3=Taobao}
则返回Values: [Google, Runoob, Taobao]

2、HashMap的相关例题

2.1、题目介绍

原题链接：128. 最长连续序列 - 力扣（LeetCode）

示例 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 <= nums.length <= 105
-109 <= nums[i] <= 109

2.2、解题

2.2.1、解题思路

使用一个HashMap存储当前遍历过的数字，如果hashMap中已经存在这个数字，说明之前已经处理过这个数字，不做任何处理【是为了防止出现重复数字再次计算造成错误】
每次遍历到新数字时，去hashMap中寻找比它小1的数字和比它大1的数字对应的长度，记为min和max。
如果min、max均为0，说明此时不存在上下界，直接记为1.
当出现min、max不为0时，说明与当前数字有新的上下界，计算出上下界所对应的数字，并在map中修改对应的上下界大小。

若不存在上下界：直接更新为1；
若存在上界不存在下界：更新上界数字长度+1，即max + 1；
若存在下界不存在上界：更新下界数字长度+1，即min + 1；
若上下界均存在：同时更新上下界长度为下界长度+上界长度+1，即min + max + 1

2.2.2、解题图解

数组nums从i=0开始遍历，has为哈希表，result用来保存最后的结果，min用来保存键值（key）为 nums[ i-1 ] 在哈希表中所对应的值（value）；max用来保存键值（key）为 nums[ i+1 ] 在哈希表中所对应的值（value），now保存当前循环最长连续序列的结果用于和result进行比较

当前的 i = 0 ,nums[ i ] = 100, has 中没有 key 为 100 的项，所以让 min = has.getOrDefault(nums[i]-1, 0)；max = has.getOrDefault(nums[i]+1, 0)；由于 has 中没有 key 为 99(nums[i]-1) 的项, 所以 min = 0 ；由于 has 中没有 key 为 101(nums[i]+1) 的项, 所以 max = 0 ；因此 now = 1 ；然后在 has 中添加 key = 100，value = 1 的项；result 小于 now，所以让 result = now = 1

当前的 i = 1 ,nums[ i ] = 4, has 中没有 key 为 4 的项，所以让 min = has.getOrDefault(nums[i]-1, 0)；max = has.getOrDefault(nums[i]+1, 0)；由于 has 中没有 key 为 3(nums[i]-1) 的项, 所以 min = 0 ；由于 has 中没有 key 为 5(nums[i]+1) 的项, 所以 max = 0 ；因此 now = 1 ；然后在 has 中添加 key = 4，value = 1 的项；result 等于 now，所以 result 不变

当前的 i = 2 ,nums[ i ] = 200, has 中没有 key 为 200 的项，所以让 min = has.getOrDefault(nums[i]-1, 0)；max = has.getOrDefault(nums[i]+1, 0)；由于 has 中没有 key 为 199(nums[i]-1) 的项, 所以 min = 0 ；由于 has 中没有 key 为 201(nums[i]+1) 的项, 所以 max = 0 ；因此 now = 1 ；然后在 has 中添加 key = 200，value = 1 的项；result 等于 now，所以 result 不变

当前的 i = 3 ,nums[ i ] = 1, has 中没有 key 为 1 的项，所以让 min = has.getOrDefault(nums[i]-1, 0)；max = has.getOrDefault(nums[i]+1, 0)；由于 has 中没有 key 为 0(nums[i]-1) 的项, 所以 min = 0 ；由于 has 中没有 key 为 2(nums[i]+1) 的项, 所以 max = 0 ；因此 now = 1 ；然后在 has 中添加 key = 1，value = 1 的项；result 等于 now，所以 result 不变

当前的 i = 4 ,nums[ i ] = 3, has 中没有 key 为 3 的项，所以让 min = has.getOrDefault(nums[i]-1, 0)；max = has.getOrDefault(nums[i]+1, 0)；由于 has 中没有 key 为 2(nums[i]-1) 的项, 所以 min = 0 ；由于 has 中有 key 为 4(nums[i]+1) 的项, 所以 max = 1 ；因此 now = 2 ；然后在 has 中添加 key = 3，value = 2 的项，添加 key = 3 + 1， value = 2 的项（has.put(nums[i]+max, now)）；result 小于 now，所以让 result = now = 2

当前的 i = 5 ,nums[ i ] = 2, has 中没有 key 为 2 的项，所以让 min = has.getOrDefault(nums[i]-1, 0)；max = has.getOrDefault(nums[i]+1, 0)；由于 has 中有 key 为 1(nums[i]-1) 的项, 所以 min = 1 ；由于 has 中有 key 为 3(nums[i]+1) 的项, 所以 max = 2 ；因此 now = 4 ；然后在 has 中添加 key = 2，value = 4 的项，添加 key = 2 + 1， value = 4 的项（has.put(nums[i]+max, now)），添加 key = 2 - 1， value = 4 的项（has.put(nums[i]-min, now)）；result 小于 now，所以让 result = now = 4

最后返回 result ，result 等于 4

2.3、解题代码

class Solution {
    public int longestConsecutive(int[] nums) {
        HashMap<Integer, Integer> has = new HashMap<>();
        int result = 0;
        for (int i=0; i<nums.length; i++){
            if (has.get(nums[i]) != null){
                continue;
            }
            int min = has.getOrDefault(nums[i]-1, 0);
            int max = has.getOrDefault(nums[i]+1, 0);
            int now = min + max + 1;
            if (min == 0 && max == 0){
                has.put(nums[i], now);
            } else if (min == 0){
                has.put(nums[i]+max, now);
                has.put(nums[i], now);
            } else if (max == 0){
                has.put(nums[i], now);
                has.put(nums[i]-min, now);
            } else{
                has.put(nums[i]+max, now);
                has.put(nums[i], 1);
                has.put(nums[i]-min, now);
            }
            result = Math.max(result,now);
        }
        return result;
    }
}

时间复杂度: O(n)

空间复杂度: O(n)

【LeetCode力扣】相关：

【LeetCode力扣】42.接雨水（困难）-CSDN博客https://blog.csdn.net/m0_65277261/article/details/134291521?spm=1001.2014.3001.5502【LeetCode力扣】287.寻找重复数（中等）-CSDN博客https://blog.csdn.net/m0_65277261/article/details/134232926?spm=1001.2014.3001.5502【LeetCode力扣】11. 盛最多水的容器（中等）-CSDN博客https://blog.csdn.net/m0_65277261/article/details/134102596?spm=1001.2014.3001.5502