LeetCode算法（哈希）

今天的算法内容是哈希相关的题目，难度比数组和链表大，但是可能我习惯了python的字典，hash的理解更容易一些，大家如果不知道hash的概念，请自行搜一下大佬们的讲解，我叙述的没他们好，那么下面就开始今天的练习

1.有效字母异位词

链接：有效字母异位词

简述一下目标，比如说有 abc ，cab

字母abc 和 字母cab 的字母个数是一样的

都是 a：1    b：1  c：1

这样的词称为异位词，我们需要写出一个算法来判断两个字母是否为异位词

思路：

（1）建立一张hash表，key为字母，value为字母出现的次数

（2）遍历任意一个字符串，将遍历到的字母，对应的value值+1，证明该字母出现过一次

（3）遍历另一个字符串，将遍历到的字母，对应的value值-1

（4）遍历hash表，查看所有的value值是否存在为0的，如果都为0则证明是异位词，反之不是

注意：

这里hash表中的key，其实并不是真正的字母，而是通过映射来对应字母，因为hash表的本质还是一个数组，所以我们通过字母与索引的映射来一一对应。每个字母有自己的 ASCII 。通过ASCII来进行映射关系，而hash也是通过数组来体现。

举例：

字母a - 字母a = 0

字母b - 字母a = 1

字母c - 字母a = 2......以此类推

所以，索引0-25，对应的就是26个字母。代码如下：

public class LetterEctopicWords {/*** 字母异位词*/public boolean isAnagram(String s, String t) {int[] record = new int[26];for (int i = 0; i < s.length(); i++) {int num = s.charAt(i) - 'a';record[num]++;}for (int i = 0; i < t.length(); i++) {int num = s.charAt(i) - 'a';record[num]--;}for (int j : record) {if (j != 0) {return false;}}return true;}}

2.两个数组的交集

链接：两个数组的交集

这里需要新知道一个hash的数据结构，hashSet，Set简单一句话总结就是无序不重复的集合，主要的作用就是去重，知道这个概念就可以继续往下进行了

比如两个数组：[1221]，[22]，它们的交集就是[2]

思路：引入set后，可以将一个数组进行第一波去重处理，然后遍历第二个数组，和去重后的第一个数组进行比较，如果相同，则添加到结果集set中，不相同则跳过，最后遍历set结果集，添加到数组进行返回即可

import java.util.HashSet;
import java.util.Set;public class IntersectionOfTwoArrays {/*两个数组的交集*/public int[] intersection(int[] nums1, int[] nums2) {//首先是创建一个set集合用于存放唯一元素//遍历第二个数组，在set集合取值进行判断，如果存在，则放入数组，如果不存在则不做操作Set<Integer> set1 = new HashSet<>();Set<Integer> set2 = new HashSet<>();for (int num : nums1) {set1.add(num);}for (int num : nums2){if (set1.contains(num)){set2.add(num);}}int[] result = new int[set2.size()];int index = 0;for (int i : set2) {result[index] = i;index++;}return result;}
}

3.两数之和

链接：两数之和

这道题就正式的需要hashMap了，也就是键值对，在使用之前需要说一下，该如何判断什么时候使用hashmap。

首先就是，既需要目标的数据，还需要目标的索引，或者是其他的两个条件，这种时候就要使用hashmap了。

简单说一下题目

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

这里发现，既需要获取数组的元素，又需要获取元素的索引，所以考虑使用hashmap

当我们拿到一个元素，例如2时，我们需要找到 9 - 2 也就是 7 ，去配对，那么就可以写代码了

思路：

（1）首先需要一个hashmap，key为元素的值，value为对应的索引

（2）遍历数组，并计算当前元素与目标结果的差值

（3）判断map中是否含有该差值，如果有则获取其索引和当前元素索引，返回

（4）如果没有，则把当前元素放入到map表中。

代码如下：

import java.util.HashMap;
import java.util.Map;public class SumOfTwoNumbers {/*两数之和*///使用哈希表public int[] twoSum(int[] nums, int target) {//首先定义一个返回值，为两个长度的数组，存储两个数的下标//定义一个hashmap，key为数，value为该数的下标//遍历数组，并计算当前数值与target的差值，如果差值已经在hashmap里了，直接返回//如果不在，则将当前数值及索引放入hashmapint[] result = new int[2];HashMap<Integer,Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++){int complement = target - nums[i];if (map.containsKey(complement)){result[0] = map.get(complement);result[1] = i;return result;}map.put(nums[i],i);}return null;}
}

4.字母异位词分组 

链接：字母异位词分组

异位词还是和第一道题一样

例子：

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
输出:
[
[“ate”,“eat”,“tea”],
[“nat”,“tan”],
[“bat”]
]

从示例发现，每个异位词其实只有一种分类，比如说e,a,t这三个字母，排序过后就是aet，其他有这三个字母的字符串，经过排序后，都会变成aet，那么只需要将所有的字符串排序，并找到自己对应排序后的异位词就可以了。

思路：

（1）构建一个map，key为排序后的字符串，value为对应异位词的集合

（2）遍历数组，取每个字符串

（3）将字符串进行排序，并在map中进行匹配

（4）如果没有，例如第一个字符串进入时，map一定是空的，则将排序后的字符串放入，并将自己放入到其对应的value中，而有的情况直接放入就好，所以先判断是否存在，不存在直接放入，然后再把自己添加进去

（5）返回map中所有的value

代码如下：

import java.util.*;public class AlphabetHeterotopicWordGrouping {/*字母异位词分组*/public List<List<String>> groupAnagrams(String[] strs) {//思路：//首先新建一个hashmap，key值为排序后的字符串，value为对应的集合//然后遍历字符串数组，将字符串进行排序//判断hashmap中是否有对应排序后的字符串，如果没有，则以当前排序后的字符串为key，新建一个集合为value//然后获取hashmap的对应键的value集合，将当前字符串添加进去HashMap<String,List<String>> hashMap = new HashMap<>();for (String str : strs){char[] chars = str.toCharArray();Arrays.sort(chars);String sortStr = new String(chars);if (!hashMap.containsKey(sortStr)){hashMap.put(sortStr,new ArrayList<String>());}//自己也需要添加到排序后的集合中hashMap.get(sortStr).add(str);}return new ArrayList<>(hashMap.values());}}

5.最长连续序列

链接：最长连续序列

例子：

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

看到这题，第一个想法就是，先排序，其次是去重，因为连续序列一定是从小到大的，且唯一

第二就是连续的条件， 后者 - 1 = 前者。

第三就是 全局最大值 和 一部分数的最大值的变化，记录一部分的最大值，并更新全局最大值

思路：

（1）使用Hashset，先对数组进行去重，然后排序

（2）将HashSet转变为list，方便后续遍历

（3）设置最大连续值 = 0，和部分最大连续值变量 = 1（因为一个数字也算）

（4）设置条件，如果，后者 - 1 = 前者。认为是连续，将部分最大连续值+1

（5）如果不是连续，将更新全局最大值，并将部分最大连续值重置

（6）最后更新全局最大值，返回

代码如下：

import java.util.*;public class LongestContinuousSequence {/*最长连续序列*/public int longestConsecutive(int[] nums) {//使用Hashset，先对数组进行去重，然后排序//使用变量来记录当前最长序列，和当前序列长度，如果当前值减去前一个值为1，则为连续，变量自增//如果不为1，则证明不是连续，当前序列长度变为1，最后比较最长序列和当前序列长度Set<Integer> integerSet = new HashSet<>();for (int num : nums) {integerSet.add(num);}// 将 HashSet 转换为 List 并排序List<Integer> sortList = new ArrayList<>(integerSet);Collections.sort(sortList);// 如果列表为空，返回 0if (sortList.size() == 0) {return 0;}// 变量声明int longSequence = 0;int nowSequence = 1;// 计算最长连续序列for (int i = 1; i < sortList.size(); i++) {if (sortList.get(i) == sortList.get(i - 1) + 1) {nowSequence++;} else {longSequence = Math.max(longSequence, nowSequence);nowSequence = 1;}}// 更新最长连续序列longSequence = Math.max(longSequence, nowSequence);return longSequence;}}

今天有关hash的差不多就到这里了，有不对不理解的地方请指出！谢谢大家