概念
哈希表（Hash Table）用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来的一种数据结构。
散列表用的就是数组支持按照下标随机访问的时候，时间复杂度是 O(1) 的特性。我们通过散列函数把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，我们用同样的散列函数，将键值转化数组下标，从对应的数组下标的位置取数据。
作业题
242. 有效的字母异位词
package jjn.carl.hashtable; /** * @author Jjn * @since 2023/7/3 14:18 */ public class LeetCode242 { public boolean isAnagram(String s, String t) { if (s == null && t == null) { return true; } if (s == null || t == null) { return true; } if (s.length() != t.length()) { return false; } char[] firstIndex = new char[26]; for (char c : s.toCharArray()) { firstIndex[c - 'a']++; } char[] secondIndex = new char[26]; for (char c : t.toCharArray()) { secondIndex[c - 'a']++; } for (int i = 0; i < firstIndex.length; i++) { if (firstIndex[i] != secondIndex[i]) { return false; } } return true; } public static void main(String[] args) { System.out.println("new LeetCode242().isAnagram(\"rat\", \"tar\") = " + new LeetCode242().isAnagram("rat", "tar")); } }
349. 两个数组的交集
package jjn.carl.hashtable; import java.util.Arrays; import java.util.HashSet; import java.util.Set; /** * @author Jjn * @since 2023/7/3 14:40 */ public class LeetCode349 { public int[] intersection(int[] nums1, int[] nums2) { boolean[] numCount = new boolean[1001]; for (int j : nums1) { numCount[j] = true; } Set<Integer> result = new HashSet<>(); for (int j : nums2) { if (numCount[j]) { result.add(j); } } int[] res = new int[result.size()]; int i = 0; for (Integer num : result) { res[i] = num; i++; } return res; } public static void main(String[] args) { int[] nums1 = new int[]{2, 3, 4, 4}; int[] nums2 = new int[]{3, 4, 4, 5, 5}; int[] intersection = new LeetCode349().intersection(nums1, nums2); System.out.println("Arrays.toString(intersection) = " + Arrays.toString(intersection)); } }
202. 快乐数
package jjn.carl.hashtable; import java.util.HashSet; import java.util.Set; /** * @author Jjn * @since 2023/7/3 17:11 */ public class LeetCode202 { public boolean isHappy(int n) { Set<Integer> existed = new HashSet<>(); while (n != 1 && existed.add(n)) { n = getNextNumber(n); } return n == 1; } private int getNextNumber(int n) { int total = 0; while (n > 0) { int rest = n % 10; total += rest * rest; n = n / 10; } return total; } public static void main(String[] args) { System.out.println("new LeetCode202().isHappy(19) = " + new LeetCode202().isHappy(19)); System.out.println("new LeetCode202().isHappy(2) = " + new LeetCode202().isHappy(2)); } }
1. 两数之和
package jjn.carl.hashtable; import java.util.Arrays; import java.util.HashMap; import java.util.Map; /** * @author Jjn * @since 2023/7/3 19:04 */ public class LeetCode1 { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer val = map.get(target - nums[i]); if (val != null) { return new int[]{val, i}; } map.put(nums[i], i); } return new int[]{}; } public static void main(String[] args) { int[] nums = new int[]{2, 7, 11, 15}; int target = 9; int[] result = new LeetCode1().twoSum(nums, target); System.out.println("Arrays.toString(result) = " + Arrays.toString(result)); } }
