哈希表，又称为散列表，是一种可以根据关键字（码值）快速实现查找、插入和删除的存储结构。结合了数组和链表的优点。
哈希函数：是hash表的映射函数：关键确定映射关系！
哈希算法：哈希算法是一类算法的统称，简单说，一段信息经过哈希算法可以映射为固定长度的数字串（对数组区间取模）。
哈希碰撞：不同的输入数据产生了相同的哈希值。解决方式：拉链法和线性探测法。
1.两数之和（1-easy）
题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。假设每种输入只会对应一个答案。
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 输入：nums = [3,3], target = 6 输出：[0,1]
思路：本题可以使用暴力法和hash映射解决。
法1.遍历两遍数组，返回找到和为目标值的两个整数，实现简单。
法2.hashmap：使用hashmap存储数组元素与索引之间的映射，遍历数组将映射加入map，当出现另一个元素，返回他们的标。
代码实现：
class Solution { // 暴力法O(n^2) public int[] twoSum(int[] nums, int target) { int n = nums.length; for (int i = 0; i < n; i++) { int num = target - nums[i]; for (int j = i + 1; j < n; j++) { if (nums[j] == num) { return new int[] {i, j}; } } } return null; } // hashmap<元素：索引> public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> map = new HashMap<>(); int n = nums.length; for (int i = 0; i < n; i++) { if (map.containsKey(target - nums[i])) { return new int[] {map.get(target - nums[i]), i}; } map.put(nums[i], i); } return null; } }
2.存在重复元素（217-easy）
题目描述：给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例：
输入: [1,2,3,1] 输出: true 输入: [1,2,3,4] 输出: false
思路：本题只判断数组中有无重复元素，可以使用hashmap映射和hashset集合元素唯一性进行判断。
- 法1.hashmap：常规是遍历数组，建立hashmap数组元素与出现次数的映射，判断是否某个元素出现次数大于1；
- 法2.hashset：利用set集合存储元素的特性（严格无重复元素），判断集合和原数组大小判断是否含有重复元素。
- 法3：排序
代码实现：
class Solution { // hashset public boolean containsDuplicate(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } return set.size() < nums.length; } // hashmap public boolean containsDuplicate(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); if (map.get(num) > 1) { return true; } } return false; } // 排序 public boolean containsDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i - 1] == nums[i]) { return true; } } return false; } }
3.最长和谐序列（594-easy）
题目描述：和谐序列，元素的最大值和最小值之间的差别正好是1。在所有可能的子序列中找到【最长的和谐子序列的长度】。
示例：
输入: [1,3,2,2,5,2,3,7] 输出: 5 原因: 最长的和谐数组是：[3,2,2,2,3]，区分子串（子串是连续的一段）！
思路：本题关键是如何获取所有可能子序列，并记录最长的子序列。使用hashmap：
- 可以遍历数组，使用hashmap映射元素与出现的次数；
- 遍历map所有键（map.keySet()），根据和谐子序列的定义，更新最长子序列长度。
优化：当加入num映射，判断map是否出现num + 1和num - 1（tips），num与前后位置都可能构成结果，更新最大值。
代码实现：
class Solution { // hashmap<元素，出现次数> public int findLHS(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } int max = 0; for (int key : map.keySet()) { if (map.containsKey(key + 1)) { max = Math.max(max, map.get(key) + map.get(key + 1)); } } return max; } // 优化（效率不高，引入过多判断） public int findLHS(int[] nums) { HashMap<Integer, Integer> map = new HashMap<>(); int max = 0; for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); if (map.containsKey(num - 1)) { max = Math.max(max, map.get(num) + map.get(num - 1)); } if (map.containsKey(num + 1)) { max = Math.max(max, map.get(num) + map.get(num + 1)); } } return max; } }
4.最长连续序列（128-hard）
题目描述：给定一个未排序的整数数组 nums ，找出数字连续（即步长为1）的最长序列（不要求序列元素在原数组中连续）的长度。要求：时间复杂度为 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)，注意点：1.结果元素唯一性（去重） 2.原始数组未排序 3.保证结果为连续子序列（步长1）。
法1.hashset：
- 首先使用hashset元素去重。
- 遍历集合，寻找被切割的连续子序列片段。关键：找到每个片段的起始元素！更新最大长度和当前元素。
法2.hashmap：使用map建立当前值与是否被标记之间的映射，递归的去寻找连续子序列片段的长度！
代码实现：
class Solution { // hashset去重+连续子序区间起始元素 public int longestConsecutive(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } int ans = 0; for (int num : set) { if (!set.contains(num - 1)) { // 找到当前子序列的开始元素 int curNum = num; int curLen = 1; while (set.contains(curNum + 1)) { curNum++; curLen++; } ans = Math.max(ans, curLen); } } return ans; } // hashmap:<元素，是否被标记> 递归的去搜索 public int longestConsecutive(int[] nums) { HashMap<Integer, Boolean> map = new HashMap<>(); for (int num : nums) { map.put(num, false); } int ans = 0; for (int num : map.keySet()) { if (!map.get(num)) { // 未标记过更新 ans = Math.max(ans, dfs(map, num)); } } return ans; } private int dfs(HashMap<Integer, Boolean> map, int num) { if (map.containsKey(num) && !map.get(num)) { map.put(num, true); return 1 + dfs(map, num - 1) + dfs(map, num + 1); } else { return 0; } } }
5.有效的字母异位词（242-easy）
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。假设字符串只包含小写字母。要求:如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
示例：
输入: s = "anagram", t = "nagaram" 输出: true
思路：本题关键是判断两个字符串是否具有相同字符，可以使用ascii码进行计数比较，也可以使用hashmap进行元素数目统计。
- ascii码计数：定义一个数组，数组存放小写字母出现的个数。
- hashmap计数：map中键值对存放每个字母和出现的个数。
代码实现：
class Solution { // ascii计数 public boolean isAnagram(String s, String t) { int[] counts = new int[26]; for (char cs : s.toCharArray()) { counts[cs - 'a']++; } for (char ct : t.toCharArray()) { counts[ct - 'a']--; } for (int i : counts) { if (i != 0) { return false; } } return true; } // hashmap public boolean isAnagram(String s, String t) { HashMap<Character, Integer> map = new HashMap<>(); for (char cs : s.toCharArray()) { map.put(cs, map.getOrDefault(cs, 0) + 1); } for (char ct : t.toCharArray()) { map.put(ct, map.getOrDefault(ct, 0) - 1); if (map.get(ct) == -1) { return false; } } return s.length() == t.length(); } }
6.两数组的交集（349-easy）
题目描述：给定两个数组，编写一个函数来计算它们的交集。
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
示例：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
思路：都要用set进行去重。
- 双Set集合：先遍历一个数组存入集合作为父集合，遍历另一个数组，将交集作为子集合（即结果）。
- 排序+双指针：先排序，在遍历两个数组，将两数组相同的元素存入集合。
- 二分查找+Set：对其中一个数组进行排序，然后进行二分查找（数组必须有序），同时，遍历另一个数组，用集合存储结果。
代码实现：
class Solution { // 双set public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> parentSet = new HashSet<>(); HashSet<Integer> childSet = new HashSet<>(); for (int num : nums1) { parentSet.add(num); } for (int num : nums2) { if (parentSet.contains(num)) { childSet.add(num); } } int[] ans = new int[childSet.size()]; int i = 0; for (int num : childSet) { ans[i++] = num; } return ans; } // 排序 + 双指针 + set public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); HashSet<Integer> set = new HashSet<>(); int i = 0, j = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { set.add(nums1[i]); i++; j++; } else if (nums1[i] > nums2[j]) { j++; } else { i++; } } int[] ans = new int[set.size()]; int index = 0; for (int num : set) { ans[index++] = num; } return ans; } // 二分查找 + set public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> set = new HashSet<>(); Arrays.sort(nums2); for (int target : nums1) { if (binarySearch(nums2, target) && !set.contains(target)) { set.add(target); } } int[] ans = new int[set.size()]; int index = 0; for (int num : set) { ans[index++] = num; } return ans; } private boolean binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { return true; } else if (nums[mid] > target) { right = mid - 1; } else { left = mid + 1; } } return false; } }
7.两数组的交集II（350-easy）
题目描述：与上题不同的是，本题结果考虑重复元素，与两数组中出现次数较小值一致。
进阶问题：
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
示例：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
思路：输出结果可以含有重复元素，可以使用hashmap<元素，出现次数>，当第二个数组包含这个元素，并且元素出现的次数>0，记录结果。
- 对于进阶问题1：已经排序的数组，可以使用双指针 + list，如上题一样（自行实现）。
- 对于进阶问题2：两数组相差比较大，利用hashmap计数，一个hash计数，另一个hash来寻找。
- 对于进阶问题3：由于内存有限，故hashmap计数不能用（耗内存）；涉及外部排序，首先想到归并排序，降低空间复杂度。
代码实现：
class Solution { public int[] intersect(int[] nums1, int[] nums2) { List<Integer> list = new ArrayList<>(); HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums1) { map.put(num, map.getOrDefault(num, 0) + 1); } for (int num : nums2) { if (map.containsKey(num) && map.get(num) > 0) { list.add(num); map.put(num, map.getOrDefault(num, 0) - 1); } } int[] ans = new int[list.size()]; int index = 0; for (int i : list) { ans[index++] = i; } return ans; } }
