文章目录
哈希表理论基础概念类型
242.有效的字母异位词解题思路源码
349. 两个数组的交集解题思路源码
202. 快乐数解题思路源码
1. 两数之和解题思路源码
总结
哈希表理论基础
概念
哈希表（散列表）中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。 主要用来快速判断一个元素是否出现集合里。 通过哈希函数将每一个元素取模放在数组对应下标中，如果出现下标一致的情况（哈希碰撞）可使用拉链法（设置链表）或线性探测法（向后移动）解决
类型
常用的三种实现哈希表的数据结构：数组、集合（set）、映射（map）
242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”输出: true
示例 2:
输入: s = “rat”, t = “car”输出: false
提示:
1 <= s.length, t.length <= 5 * 104s 和 t 仅包含小写字母
解题思路
典型的哈希表题目，如果暴力解法直接两个for循环时间复杂度为O（n²），耗时太长。由于题干给出只有小写字母，可以定义一个长度为26的数组，遍历s和t，s的每个字母在对应下标加一，t的每个字母在对应下标减一，最后循环看数组中是否有不为0的元素。
源码
class Solution {
public boolean isAnagram(String s, String t) {
int[] letter = new int[26];
int n=0, m=0;
if(s.length() != t.length()){
return false;
}
for(int i = 0; i n=s.charAt(i)-97; letter[n]++; m=t.charAt(i)-97; letter[m]--; } for(int i=0; i<26; i++){ if(letter[i]!=0){ return false; } } return true; } } 时间复杂度: O(n) 空间复杂度: O(1) 349. 两个数组的交集 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2] 示例 2： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4]解释：[4,9] 也是可通过的 提示： 1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000 解题思路 由于本题给定了数大小的限制范围，所以可以使用数组，但是数据太散导致了空间的极大浪费，这种情况下可以使用集合（set）来构建哈希表，可以有效节省空间。 源码 数组 class Solution { public int[] intersection(int[] nums1, int[] nums2) { int[] result = new int[1000]; int sum=0; for(int i = 0; i int n=nums1[i]; if(result[n]!=1){ result[n]=1; } } for(int i=0; i int n=nums2[i]; if(result[n]==1){ result[n]=2; sum++; } } int[] num = new int[sum]; int m=0; for(int i=0; i if(result[i]==2){ num[m]=i; m++; } } return num; } } 集合 import java.util.HashSet; import java.util.Set; class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set Set //遍历数组1 for (int i : nums1) { set1.add(i); } //遍历数组2的过程中判断哈希表中是否存在该元素 for (int i : nums2) { if (set1.contains(i)) { resSet.add(i); } } return resSet.stream().mapToInt(x -> x).toArray(); } } 时间复杂度: O(m + n) 空间复杂度: O(n) 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 解题思路 因为题干说明了可能出现无限循环，那么就会出现答案重复的情况，只要用哈希表保存答案，出现重复答案就返回FALSE就可以。典型的set型哈希表题目。 源码 import java.util.HashSet; import java.util.Set; class Solution { public boolean isHappy(int n) { Set int result = n; while(1==1){ result=getSum(result); if(result==1){ return true; } else if(num.contains(result)){ return false; } num.add(result); } } private int getSum(int n){ int sum=0; while (n>=1) { sum += (n % 10) * (n % 10); n /= 10; } return sum; } } 时间复杂度: O(logn) 空间复杂度: O(logn) 1. 两数之和 解题思路 源码 暴力解法 class Solution { public int[] twoSum(int[] nums, int target) { int n=nums.length; for(int i=0; i for(int j=i+1; j if(nums[i]+nums[j]==target){ return new int[] {i,j}; } } } int[] res = new int[0]; return res; } } 时间复杂度: O(n²) 空间复杂度: O(1) 哈希表（Map） class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; Map for(int i=0; i int temp = target-nums[i]; if(map.containsKey(temp)){ res[0]=i; res[1]=map.get(temp); break; } map.put(nums[i], i); } return res; } } 时间复杂度: O(n) 空间复杂度: O(n) 总结 哈希表是一种很经典的用空间换时间的方法，主要用于快速检索某个值是否出现在集合中，避免了检索需要遍历集合的时间消耗。 java底层对于set和map的实现原理之类的知识点还是要好好复习一下，继续加油！ 精彩链接
发表评论