HashMap存储相关（多用来存储唯一性数据，或数据数量的使用）
数组中重复的数字
由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的
数字即返回。为了判断一个数字是否重复遇到，使用集合存储已经遇到
的数字，如果遇到的一个数字已经在集合中，则当前的数字是重复数字。
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<Integer>();
int repeat = -1;
for (int num : nums) {
if (!set.add(num)) {
repeat = num;
break;
}
}
return repeat;
}
第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
本题考察 哈希表 的使用，本文介绍 “哈希表” 和 “有序哈希表” 两种解法。其中
，在字符串很长时， “有序哈希表” 解法理论上效率更高。
public char firstUniqChar(String s) {
HashMap<Character, Boolean> dic = new HashMap<>();
char[] sc = s.toCharArray();
for(char c : sc)
dic.put(c, !dic.containsKey(c));
for(char c : sc)
if(dic.get(c)) return c;
return ' ';
}
在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。
基于此，可通过遍历有序哈希表，实现搜索首个 “数量为 1 的字符”。
public char firstUniqChar(String s) {
Map<Character, Boolean> dic = new LinkedHashMap<>();
char[] sc = s.toCharArray();
for(char c : sc)
dic.put(c, !dic.containsKey(c));
for(Map.Entry<Character, Boolean> d : dic.entrySet()){
if(d.getValue()) return d.getKey();
}
return ' ';
}
两个数组的交集
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，
然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，
则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现
的次数，然后遍历较长的数组得到交集。
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
复制带随机指针的链表
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
public Node copyRandomList(Node head) {
if(head==null) {
return null;
}
//创建一个哈希表，key是原节点，value是新节点
Map<Node,Node> map = new HashMap<Node,Node>();
Node p = head;
//将原节点和新节点放入哈希表中
while(p!=null) {
Node newNode = new Node(p.val);
map.put(p,newNode);
p = p.next;
}
p = head;
//遍历原链表，设置新节点的next和random
while(p!=null) {
Node newNode = map.get(p);
//p是原节点，map.get(p)是对应的新节点，p.next是原节点的下一个
//map.get(p.next)是原节点下一个对应的新节点
if(p.next!=null) {
newNode.next = map.get(p.next);
}
//p.random是原节点随机指向
//map.get(p.random)是原节点随机指向 对应的新节点
if(p.random!=null) {
newNode.random = map.get(p.random);
}
p = p.next;
}
//返回头结点，即原节点对应的value(新节点)
return map.get(head);
}
判断链表中是否有环
我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表。
public boolean hasCycle(ListNode head) {
Set<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
找树中两个指定节点的最近公共祖先。
哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点
开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已
经访问过的节点，那么这个节点就是我们要找的最近公共祖先。
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set<Integer> visited = new HashSet<Integer>();
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {
return q;
}
q = parent.get(q.val);
}
return null;
}
}
缺失数字
给定一个包含 0, 1, 2, ..., n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
public int missingNumber(int[] nums) {
Set<Integer> numSet = new HashSet<Integer>();
for (int num : nums) numSet.add(num);
int expectedNumCount = nums.length + 1;
for (int number = 0; number < expectedNumCount; number++) {
if (!numSet.contains(number)) {
return number;
}
}
return -1;
}
找出最长连续序列的长度（通过将数组中的数字放入set中，然后遍历数组，查找set中是否有连续的序列）
public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
int longestStreak = 0;
for (int num : num_set) {
if (!num_set.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;
while (num_set.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak);
}
}
return longestStreak;
}
扑克牌中的顺子
遍历五张牌，遇到大小王（即 0直接跳过。
判别重复： 利用 Set 实现遍历判重， Set
获取最大 / 最小的牌： 借助辅助变量 ma 和 mi ，遍历统计即可。
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
四数相加（HashMap存一组，另一组和HashMap进行比对）
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组和为0
采用分为两组，HashMap存一组，另一组和HashMap进行比对。
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
for(int i = 0;i<A.length;i++){
for(int j= 0;j<B.length;j++){
int sumAB = A[i]+B[j];
if(map.containsKey(sumAB)) map.put(sumAB,map.get(sumAB)+1);
else map.put(sumAB,1);
}
}
for(int i = 0;i<C.length;i++){
for(int j = 0;j<D.length;j++){
int sumCD = -(C[i]+D[j]);
if(map.containsKey(sumCD)) res += map.get(sumCD);
}
}
return res;
}
至少有K个重复字符的最长子串
先用hash表统计s中每个字符出现的次数，显然如果字符c出现的次数小于k
，c必然不在最长子串里面，根据这个特性可以将原始s分割成多个子串递归地求解问
题，我们用一个split数组依次来存放每个分割点的索引，对每个分割区间同样求
解该问题(多路的分治问题)，并取结果的最大值保存在变量ans中，此处有一个小trick
（如果当前求解的子串长度比已存在的ans还要小，则没有必要求解
该区间，这样可以减少不必要的计算），最后递归的结束点就是当前求
解的字符串s符合最长子串的要求。
public:
int longestSubstring(string s, int k) {
unordered_map<char, int> umap;
for (auto c : s) umap[c]++;
vector<int> split;
for (int i = 0; i < s.size(); i++) {
if (umap[s[i]] < k) split.push_back(i);
}
if (split.size() == 0) return s.length();
int ans = 0, left= 0;
split.push_back(s.length());
for (int i = 0; i < split.size(); i++) {
int len = split[i] - left;
if (len > ans) ans = max(ans, longestSubstring(s.substr(left, len), k));
left = split[i]+1;
}
return ans;
}
};
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] counter = new int[26];
for (int i = 0; i < s.length(); i++) {
counter[s.charAt(i) - 'a']++;
counter[t.charAt(i) - 'a']--;
}
for (int count : counter) {
if (count != 0) {
return false;
}
}
return true;
}
给定一个字符串，找到它的第一个不重复的字符
public int firstUniqChar(String s) {
HashMap<Character, Integer> count = new HashMap<Character, Integer>();
int n = s.length();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
count.put(c, count.getOrDefault(c, 0) + 1);
}
for (int i = 0; i < n; i++) {
if (count.get(s.charAt(i)) == 1)
return i;
}
return -1;
}
最长不含重复字符的子字符串
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
dic.put(s.charAt(j), j); // 更新哈希表
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}