1 哈希表的基础

12.23 一刷

哈希表是一种基于哈希算法实现的键值对集合，提供了快速的数据插入、删除和查找功能。Java提供了HashMap、Hashtable和LinkedHashMap等实现哈希表的类。以下是Java哈希表的一些基础概念和操作：

1.1 基础概念及实现

1.2.1 哈希表的工作原理

哈希表通过哈希函数将键（Key）映射到哈希表的索引上，然后通过这个索引来访问值（Value）。如果两个键的哈希值相同（哈希冲突），则通过链表或其他方法来解决冲突。

1.2.2 705.设计哈希集合

705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

• void add(key) 向哈希集合中插入值 key 。
• bool contains(key) 返回哈希集合中是否存在这个值 key 。
• void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

class MyHashSet {/**hash函数用于将key映射到数组中用链表法来解决哈希冲突，当两个不同的数映射到数组的同一位置时，将该数接到数组位置的链表后面*///定义hash表的长度为769private static final int BASE = 769;private LinkedList[] list;public MyHashSet() {//初始化哈希表list = new LinkedList[BASE]; //初始化LinkedListfor(int i = 0;i<BASE;i++){list[i] = new LinkedList<Integer>();}}public void add(int key) {int h = hash(key);//找到key映射到hash表中的位置Iterator<Integer> iter = list[h].iterator();while(iter.hasNext()){Integer element = iter.next();if(element == key){return;}}list[h].offerLast(key);}public void remove(int key) {int h = hash(key);Iterator<Integer> iter = list[h].iterator();while(iter.hasNext()){Integer element = iter.next();if(element == key){list[h].remove(element);return;}}}public boolean contains(int key) {int h = hash(key);Iterator<Integer> iter = list[h].iterator();while(iter.hasNext()){int element = iter.next();if(element == key){return true;}}return false;}private static int hash(int key){return key % BASE;}
}/*** Your MyHashSet object will be instantiated and called as such:* MyHashSet obj = new MyHashSet();* obj.add(key);* obj.remove(key);* boolean param_3 = obj.contains(key);*/

1.2.3 706.设计哈希映射

706. 设计哈希映射

已解答

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

• MyHashMap() 用空映射初始化对象
• void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
• int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
• void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

class MyHashMap {/**感觉和上一个哈希表的题差不多，根据key映射到哈希表数组中的位置。只是此时，哈希表中的每个元素都应该后面还跟着value，不再是Integer了？*///定义一个Pairprivate class Pair{private int key;private int value;public Pair(int key,int value){this.key = key;this.value = value;}public int getKey(){return key;}public int getValue(){return value;}public void setValue(int value){this.value = value;}}private static final int BASE = 769;LinkedList[] list ;public MyHashMap() {list = new LinkedList[BASE];for(int i = 0;i<BASE;i++){list[i] = new LinkedList<Pair>();}}public void put(int key, int value) {int h = hash(key);Iterator<Pair> iter = list[h].iterator();while(iter.hasNext()){Pair pair = iter.next();if(pair.getKey()==key){pair.setValue(value);return;}}list[h].offerLast(new Pair(key,value));}public int get(int key) {int h = hash(key);Iterator<Pair> iter = list[h].iterator();while(iter.hasNext()){Pair pair = iter.next();if(pair.getKey()==key){return pair.getValue();}}return -1;}public void remove(int key) {int h = hash(key);Iterator<Pair> iter = list[h].iterator();while(iter.hasNext()){Pair pair = iter.next();if(pair.getKey()==key){list[h].remove(pair);return;}}}private int hash(int key){return key % BASE;}
}/*** Your MyHashMap object will be instantiated and called as such:* MyHashMap obj = new MyHashMap();* obj.put(key,value);* int param_2 = obj.get(key);* obj.remove(key);*/

1.2 HashMap相关

HashMap是Java中使用最广泛的哈希表实现，它基于Map接口，允许键值对中的键（Key）和值（Value）为null，并且不保证映射的顺序。

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
Integer value = map.get("key1"); // 返回1
map.remove("key2");

1.2.1 基本操作

• put(K key, V value)：将指定的值与此映射中的指定键关联。
• get(Object key)：返回指定键所映射的值。
• remove(Object key)：如果存在一个键的映射关系，则将其从映射中移除。
• keySet()：返回映射中包含的键的Set视图。
• values()：返回映射中包含的值的Collection视图。
• entrySet()：返回映射中包含的键值映射关系的Set视图

1.2.2 遍历

1. 使用 entrySet()

entrySet() 方法返回哈希表中所有键值对的 Set 视图。这个集合中的每个元素都是一个 Map.Entry 对象，其中包含键和值。

HashMap<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);
map.put("key3", 3);for (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + " => " + value);
}

2. 使用 keySet()

keySet() 方法返回哈希表中所有键的 Set 视图。通过这个集合遍历所有的键，然后使用每个键来获取对应的值。

for (String key : map.keySet()) {Integer value = map.get(key);System.out.println(key + " => " + value);
}

3. 使用 values()

如果你只对值感兴趣，可以使用 values() 方法获取哈希表中所有值的 Collection 视图。

for (Integer value : map.values()) {System.out.println(value);
}

4. 使用 forEach 增强型 for 循环（Java 8+）

Java 8 引入了 forEach 方法，它允许使用增强型 for 循环的语法来遍历 Collection。

map.forEach((key, value) -> System.out.println(key + " => " + value));

5. 使用迭代器 Iterator

使用迭代器 Iterator 来遍历哈希表可以避免在遍历时修改集合导致的 ConcurrentModificationException。

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();System.out.println(entry.getKey() + " => " + entry.getValue());
}

注意事项

• 当遍历哈希表时，如果需要修改哈希表（增加或删除元素），推荐使用迭代器 Iterator 的 remove 方法，或者在外部使用 removeIf 方法。
• entrySet()、keySet() 和 values() 返回的视图反映了哈希表的当前状态，如果哈希表被修改，视图也会相应地变化。
• 遍历哈希表的时间复杂度是 O(n)，其中 n 是哈希表中的元素数量。

1.3 Hashtable

Hashtable是遗留类，也实现了Map接口，但它是同步的，不允许键或值为null，并且它的性能通常不如HashMap。

Hashtable<String, Integer> htable = new Hashtable<>();
htable.put("key1", 1);
htable.put("key2", 2);
Integer value = htable.get("key1"); // 返回1
htable.remove("key2");

1.4 LinkedHashMap

LinkedHashMap是HashMap的一个子类，它维护了元素的插入顺序或者访问顺序，取决于构造函数的参数。

LinkedHashMap<String, Integer> lmap = new LinkedHashMap<>();
lmap.put("key1", 1);
lmap.put("key2", 2);
Integer value = lmap.get("key1"); // 返回1
lmap.remove("key2");

1.5 HashSet

HashSet 是 Java 中的一个集合类，它实现了 Set 接口，不允许集合中有重复的元素。HashSet 的行为是由 HashMap 实现的，它使用哈希表来存储元素，因此具有很高的添加、删除和搜索效率。以下是 HashSet 的一些基础知识和遍历方法：

1.5.1基本特性

• 不允许重复：HashSet 不允许存储重复元素。
• 无序：HashSet 中的元素是无序的，这意味着元素插入和取出的顺序不一定相同。
• 非线程安全：HashSet 是非线程安全的，如果需要线程安全，可以使用 Collections.synchronizedSet 或 CopyOnWriteArraySet。

1.5.2 基本方法

// 创建
HashSet<String> set = new HashSet<>();
//添加
set.add("element1");
set.add("element2");
//删除
boolean removed = set.remove("element1"); // 返回 true 如果元素被移除，false 如果元素不存在// 判断元素是否存在
boolean contains = set.contains("element1"); // 返回 true 如果元素存在，false 否则// 遍历1 
for (String element : set) {System.out.println(element);
}// 遍历2
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {String element = iterator.next();System.out.println(element);
}// 遍历3
set.forEach(element -> System.out.println(element));// 遍历4
set.stream().forEach(System.out::println);

1.5.3 注意事项

• HashSet 中的元素顺序不可预测，如果你需要有序的集合，可以考虑使用 TreeSet。
• 由于 HashSet 依赖于哈希函数，某些情况下可能会遇到哈希冲突，但 Java 的实现已经足够高效，冲突通常不会影响性能。
• 当遍历或迭代 HashSet 时，如果需要修改集合，应该使用迭代器的 remove 方法，或者在外部使用 removeIf 方法。

2 383.赎金信

383. 赎金信

简单

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

2.1 思路

简单字符可以用长度为26的数组来记录字符出现的次数

    两个哈希表记录ransomNote和magazin两个字符串中，字符出现的次数，之后再一一比较由于是简单的字符，所以可以用两个长度为26的数组来记录字符出现的次数cnt_r[26]cnt_m[26]之后遍历cnt_r中的值，判断cnt_r中的每个字符出现的数量是否大于cnt_m中该字符出现的数量。小于则直接返回false

2.2 代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {/***/int[] cnt_r = new int[26];int[] cnt_m = new int[26];for(int i = 0;i<ransomNote.length();i++){cnt_r[ransomNote.charAt(i)-'a']++;}for(int i = 0;i<magazine.length();i++){cnt_m[magazine.charAt(i)-'a']++;}for(int i = 0;i<26;i++){if(cnt_r[i]>cnt_m[i]){return false;}}return true;}
}

3 205.同构字符串

205. 同构字符串

简单

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"
输出：true

示例 2：

输入：s = "foo", t = "bar"
输出：false

示例 3：

输入：s = "paper", t = "title"
输出：true

提示：

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

3.1 思路

第一遍的时候用1个hashmap，这样会存在s->t一对一，t->s多对多的问题

两个HashMap，分别存储s-> t的映射和t-> s的映射

        用一个HashMap存储s中字符到t的映射关系，之后判断即可具体而言，对于s和t，假如是同构的，那么s中的所有字符都能映射到t中。即map[s[i]] = t[i] 会对所有的i都满足。反之，假如不满足上面条件，则说明不同构。举例s = egg,t = add遍历s和t中的每个元素，在第一个元素的时候，得出映射关系为 e->a第二个元素 g->d第三个元素 g->d，成立。具体实现则是，维持两个HashMap，分别存储s->t的映射和t->s的映射。因为一个的话会存在这种情况。s = bacdt = baba对于s中的字符满足唯一映射，但是对于t中的，比如b会映射到{b,c}不对。因此，维持两个map，s2t中以s字符为键，映射至t的字符为值t2s中以t字符为键，映射至s的字符为值从左到右遍历两个字符串，更新哈希表。出现冲突时（当前下标i对应的s[i]存在映射，但是映射不为t[i]，或者t[i]存在映射，但是映射不为s[i]）返回false

3.2 代码

class Solution {public boolean isIsomorphic(String s, String t) {/***/int n = s.length();Map<Character,Character> maps2t = new HashMap<>();Map<Character,Character> mapt2s = new HashMap<>();for(int i = 0;i<n;i++){char si = s.charAt(i);char ti = t.charAt(i);//冲突if(maps2t.containsKey(si) && maps2t.get(si) != ti){return false;}if(mapt2s.containsKey(ti) && mapt2s.get(ti) != si){return false;}maps2t.put(s.charAt(i),t.charAt(i));mapt2s.put(t.charAt(i),s.charAt(i));}return true;}
}

4 290.单词规律

290. 单词规律

简单

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

示例 2:

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

提示:

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

4.1 分析

和205.同构字符串差不多的题。简单题

4.2 代码

class Solution {public boolean wordPattern(String pattern, String s) {/**感觉和上一题一样，都是维护两个map，然后双向映射。思路差不多。*/String[] strs = s.split(" ");if(strs.length!=pattern.length()){return false;}Map<Character,String> c2strs = new HashMap<>();Map<String,Character> strs2c = new HashMap<>();for(int i = 0;i<strs.length;i++){char c = pattern.charAt(i);if(c2strs.containsKey(c) && !c2strs.get(c).equals(strs[i])){return false;}if(strs2c.containsKey(strs[i]) && strs2c.get(strs[i])!=c ){return false;}c2strs.put(c,strs[i]);strs2c.put(strs[i],c);}return true;}
}

5 242.有效的字母异位词

242. 有效的字母异位词

简单

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

5.1 思路

分析，不难

        一个cnt数组1.将s中所有出现过的字母放入cnt中记录2.遍历t，遇见一个t的字母，就在cnt中减去对应的值。假如减之后cnt值<0，则s和t的字符一定不相同。返回false3.遍历cnt，假如有不为0的数，返回false

5.2 代码

class Solution {public boolean isAnagram(String s, String t) {/***/if(s.length()!=t.length()){return false;}int[] cnt = new int[26];for(char c: s.toCharArray()){cnt[c-'a']++;}for(char c: t.toCharArray()){cnt[c-'a']--;if(cnt[c-'a']<0){return false;}}return true;}
}

6 49. 字母异位词分组

49. 字母异位词分组

中等

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

6.1 思路

重点是用Arrays.sort排序？排序后的字符串作为key

    遍历strs，对strs中的每个str，先使用Arrays.sort排序，维持一个<String,List<String>> 的Map，排序后的字符串作为Key，排序前的作为Value最后，遍历Map，取出Map中的所有Value放到List结果中

6.2 代码

class Solution {public List<List<String>> groupAnagrams(String[] strs) {/***/Map<String,List<String>> map = new HashMap<>();for(String str:strs){char[] str_c = str.toCharArray();Arrays.sort(str_c);String key = new String(str_c);List<String> list = map.getOrDefault(key,new ArrayList<String>());list.add(str);map.put(key,list);}List<List<String>> res = new ArrayList<>();for(Map.Entry<String,List<String>> entry: map.entrySet()){res.add(entry.getValue());}return res;}
}

7 1.两数之和

1. 两数之和

简单

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？

7.1 思路

经典题目，但是第一遍只想得起来暴力

1. 暴力枚举遍历
2. 用Map记录数字和他的下标。之后遍历的时候就能通过hashmap知道target-x是否出现过了。

枚举遍历要加速的话可以用空间换时间，用一个Map记录每个数字和他的下标。之后给原数组排序。然后双指针遍历。上面是一个思路。实际上是记录了之后，在遍历的时候能够借助hashmap知道target-x是否出现过。因此时间复杂度能从O（n^2）降到O（1）// int n = nums.length;// for(int i = 0;i<n;i++){//     for(int j = i+1;j<n;j++){//         if(nums[i]+nums[j]==target){//             return new int[]{i,j};//         }//     }// }// return new int[]{};

7.2 代码

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();for(int i = 0;i<nums.length;i++){if(map.containsKey(target-nums[i])){return new int[]{i,map.get(target-nums[i])};}map.put(nums[i],i);}return new int[]{};}
}

8 202.快乐数 （需要复习）

202. 快乐数

简单

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 231 - 1

8.1 思路

可以用哈希表做，用哈希表记录出现的数字，当出现重复的时候就可以返回了。

如果重复的数字为1，说明是快乐数，否则不为快乐数。

巧妙的是快慢指针判断有环的解法。具体参考下面

    快慢指针快指针每次走2步，慢指针每次走1步，二者相等时，即为1个循环周期若有环则一定能相遇，若无环也会相遇，但相遇点为1想起来了那道判断链表进环点的题。也是快慢指针。相遇后，让一个新的指针从起点开始，以和慢指针一样的速度行动，相遇的节点即为入环点。但是本题只用判断循环点是否为1即可。

8.2 代码

class Solution {public boolean isHappy(int n) {/***/int slow = n,fast = n;do{slow = bigSquareSum(slow);fast = bigSquareSum(fast);fast = bigSquareSum(fast);}while(slow != fast);if(slow==1){return true;}return false;}int bigSquareSum(int n){int sum = 0;while(n!=0){sum+= (n%10)*(n%10);n=n/10;}return sum;}
}

9 219.存在重复元素II

219. 存在重复元素 II

已解答

简单

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

9.1 思路

hashmap的应用

    维护一个HashMap,map中是nums中的值->下标的映射遍历nums，假如在遍历时发现map中存储过该值，则根据map取出上次出现的下标，计算是否满足i-j<=k,若不满足，则将当前下标更新为j

9.2 代码

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {/***/Map<Integer,Integer> map = new HashMap<>();for(int i=0;i<nums.length;i++){int num = nums[i];if(map.containsKey(num)){if(i-map.get(num)<=k){return true;}}map.put(num,i);}return false;}
}

10 128.最长连续序列

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

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

示例 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

10.1 思路

具体如下。重点是

1. 需要找到可能的连续序列 开始的数字，之后往后遍历计算最长连续序列即可。

        利用hash表来存储nums的值，帮助枚举连续的数1.先遍历nums，将nums中的值都存在hashset中2.遍历hashset，找到每个可能的连续序列开始的数，然后从该数开始往后遍历，计算最长连续序列

10.2 代码

class Solution {public int longestConsecutive(int[] nums) {/***/Set<Integer> set = new HashSet<>();for(Integer num: nums){set.add(num);}int res = 0;for(Integer num: set){//2.1 判断是不是连续序列最开始的数if(set.contains(num-1)){continue;}//2.2 说明是连续序列最开始的数int curres = 0;while(set.contains(num++)){curres++;}res = Math.max(res,curres);}return res;}
}