哈希表算法

1.1 基础知识

哈希表：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做哈希表（散列表）。哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。可以将算法思想分为两个部分：

向哈希表中插入一个关键字：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中
在哈希表中搜索一个关键字：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值

1.2 Java中的运用

Hash函数与哈希表是数据结构与算法中的基本部分。在Java中，HashMap和HashSet等集合实现了hash函数存储数据的基本方法。HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合，而 HashMap 中存储key不重复的键值对。这两种数据结构应用于解决不同的问题。

// HashMap用法简介
Map<key, value> mapper = new HashMap<>();
mapper.put(key, value); // 存放一对键值对
mapper.get(key); // 根据键获取其值
mapper.getOrDefault(key, DefaultValue); // 根据键获取值，如果哈希表中不存在该键，则返回DefaultValue，
																				// 常用来初始化每一个第一次放入哈希表中的键值
mapper.size(); // 获取哈希表中存储键值对的对数
mapper.keySet();  // 获取key集合
mapper.values();  // 获取value集合


// HashSet用法简介
Set<Integer> sites = new HashSet<>();
sites.add(value);  // 存放元素，重复的元素不会被添加
sites.remove(value); // 删除元素，成功返回true，否则为false

1.3 相关题目

使数组中所有元素都等于零

题目描述：

给你一个非负整数数组 nums 。在一步操作中，你必须：

选出一个正整数 x ，x 需要小于或等于 nums 中最小的非零元素。
nums 中的每个正整数都减去 x。

返回使 nums 中所有元素都等于 0 需要的最少操作数。

示例：

输入：nums = [1,5,0,3,5]
输出：3
解释：
第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。

输入：nums = [0]
输出：0
解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。

解题思路：通过分析题目，可以知道其实这个题目就是计算不重复的非零数的个数。因为不需要记录重复元素的个数，所以使用HashSet集合即可。

代码如下：

class Solution {
    public int minimumOperations(int[] nums) {
        Set<Integer> sites = new HashSet<>();

        for (int i=0; i < nums.length; i++){
            if (nums[i] > 0){
                sites.add(nums[i]); // 重复元素不会添加，帮助去重
            }
        }
        return sites.size();
    }
}

数组中数字出现的次数

题目描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例：

输入：nums = [3,4,3,3]
输出：4

输入：nums = [9,1,7,9,7,9,7]
输出：1

解题思路：通过分析题目，很容易想到，用HashMap<Integer, Integer>存储<数字，出现次数>，因为HashMap的特性，key值是不能重复出现的。将数组遍历一次后，再遍历HashMap，找到出现次数为一的数字。

代码如下：

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> mapper = new HashMap<>();

        for (int i=0; i < nums.length; i++){
            int value = mapper.getOrDefault(nums[i], 0);
            value ++;
            mapper.put(nums[i], value);
        }
        
        int mark = -1;
        for (Integer i: mapper.keySet()){
            if (mapper.get(i) == 1){
                mark = i;
            }
        }

        return mark;
    }
}

最长连续数列

题目描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

解题思路：一般面对这种题目，第一个想到的就是将数组排序，然后使用动态规划的方法计算每个下标处的最长序列长度（记得跳过重复的元素）。但是题目限定了时间复杂度为O(n)，因此我们可以从用空间换时间的角度去寻找答案。对于这道题目，很显然，对于最长序列x, x+1, …, x+y来说，如果要对序列中的每个数都进行遍历求其对应的最长序列是有重复运算的。因此，我们可以首先考虑使用哈希表，将数组中重复元素先去掉，然后遍历数组，对于一个数x，如果哈希集合中含有x-1这个数，则我们不去计算这个数的的最长序列，理由前面已经说过了。

代码如下：

class Solution {
    public int longestConsecutive(int[] nums) {
        // 使用哈希集合对数组进行去重,避免对相同的值进行重复的计算其最长连续数列
        Set<Integer> integers = new HashSet<>();

        for (int num:nums){
            integers.add(num);
        }

        int longCon = 0;
        int max = 0;

        // 遍历哈希集合，计算每一个值对应的最长连续数列长度，处于同一个最长连续数列的值应当跳过
        for (int num:nums){
            // 如果数组中存在num-1，则不计算当前num对应的最长连续数列避免重复运算
            // 因为num-1对应的最长序列必然比num长度要短
            if (!integers.contains(num-1)){
                int currentNum = num;
                longCon = 1;
                while (integers.contains(currentNum+1)){
                    currentNum ++;
                    longCon ++;
                }
                
                if (max < longCon){
                    max = longCon;
                }
            }
        }

        return max;
    }
}