代码随想录第五天 | 哈希表part01

穆望 · 2025-6-1 21:30:57

哈希表理论基础
建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。
什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。这句话很重要，大家在做哈希表题目都要思考这句话。
文章讲解：https://programmercarl.com/哈希表理论基础.html
242.有效的字母异位词
建议：这道题目，大家可以感受到数组用来做哈希表给我们带来的遍历之处。
题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.有效的字母异位词.html
题目感想：
1.就是相同数量的字母来组成的不同的单词嘛，我们可以通过暴力循环来得出是否是异位词，也可以通过初始化一个数组，因为全是字母且小写，所以只用26位数组就行，然后先遍历第一个字符串，在数组其对应的位置上面+1，然后再遍历第二个字符串，在数组对应位置上-1，最后再检查整个数组，看是否有不为0的位，有则不是，没有则是异位字；

/**
* 242. 有效的字母异位词字典解法
* 时间复杂度O(m+n) 空间复杂度O(1)
*/
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
record[s.charAt(i) - 'a']++;
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
}
for (int i = 0; i < t.length(); i++) {
record[t.charAt(i) - 'a']--;
}
for (int count: record) {
if (count != 0) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
return true;
// record数组所有元素都为零0，说明字符串s和t是字母异位词
}
}

复制代码

<ol start="349">两个数组的交集
建议：本题就开始考虑什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和测试用例，添加了 0  0 && hash2 > 0)             resList.add(i);       int index = 0;       int res[] = new int[resList.size()];       for(int i : resList)          res[index++] = i;       return res; }}[/code]

快乐数
建议：这道题目也是set的应用，其实和上一题差不多，就是套在快乐数一个壳子
题目链接/文章讲解：https://programmercarl.com/0202.快乐数.html

题目感想：
1.最简单的方法就是计算然后去set里面找是否出现过，没出现就存起来，直到结果为1或者出现重复的就结束；
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
      if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
         return new int[0];
      }
      Set<Integer> set1 = new HashSet<>();
      Set<Integer> resSet = new HashSet<>();
      //遍历数组1
      for (int i : nums1) {
         set1.add(i);
      }
      //遍历数组2的过程中判断哈希表中是否存在该元素
      for (int i : nums2) {
         if (set1.contains(i)) {
            resSet.add(i);
         }
      }
      //方法1：将结果集合转为数组
      return resSet.stream().mapToInt(x -> x).toArray();
      //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
      int[] arr = new int[resSet.size()];
      int j = 0;
      for(int i : resSet){
         arr[j++] = i;
      }
      return arr;
}
}
复制代码
2.还有一个方法就是用到了快慢指针，慢指针一次走一步，快指针一次走两步，之后比较他们的出的值是否有为1的或者他们的值是否相等，这样就不用存储了！！！是不是很熟悉，没错，我们在找链表中的环的时候也用到了这个，太有意思了。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
      int[] hash1 = new int[1002];
      int[] hash2 = new int[1002];
      for(int i : nums1)
         hash1[i]++;
      for(int i : nums2)
         hash2[i]++;
      List<Integer> resList = new ArrayList<>();
      for(int i = 0; i < 1002; i++)
         if(hash1[i] > 0 && hash2[i] > 0)
            resList.add(i);
      int index = 0;
      int res[] = new int[resList.size()];
      for(int i : resList)
         res[index++] = i;
      return res;
}
}
复制代码
3.还有一种是数学解法，这个就是找到一个三位数字可能会进入的循环链然后存起来，只要后面的计算的数字在这个循环链中那么就是不能为1的
class Solution {
public boolean isHappy(int n) {
      Set<Integer> record = new HashSet<>();
      while (n != 1 && !record.contains(n)) {
         record.add(n);
         n = getNextNumber(n);
      }
      return n == 1;
}
private int getNextNumber(int n) {
      int res = 0;
      while (n > 0) {
         int temp = n % 10;
         res += temp * temp;
         n = n / 10;
      }
      return res;
}
}
复制代码
感兴趣的可以去力扣看看详细的题解；

两数之和
建议：本题虽然是力扣第一题，但是还是挺难的，也是代码随想录中数组，set之后，使用map解决哈希问题的第一题。
建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.两数之和.html

题目感想：
1.简单的方法有两种，一种是在set中匹配自己需要的，匹配不到把自己加进去，然后循环；另外一种是，给这个数组排序，然后两个指针分布数组两端，根据和目标的大小进行缩进；
class Solution {
   public int getNext(int n) {
      int totalSum = 0;
      while (n > 0) {
         int d = n % 10;
         n = n / 10;
         totalSum += d * d;
      }
      return totalSum;
}
public boolean isHappy(int n) {
      int slowRunner = n;
      int fastRunner = getNext(n);
      while (fastRunner != 1 && slowRunner != fastRunner) {
         slowRunner = getNext(slowRunner);
         fastRunner = getNext(getNext(fastRunner));
      }
      return fastRunner == 1;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复制代码
class Solution {
private static Set<Integer> cycleMembers =
      new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
public int getNext(int n) {
      int totalSum = 0;
      while (n > 0) {
         int d = n % 10;
         n = n / 10;
         totalSum += d * d;
      }
      return totalSum;
}
public boolean isHappy(int n) {
      while (n != 1 && !cycleMembers.contains(n)) {
         n = getNext(n);
      }
      return n == 1;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复制代码
[code]//使用双指针public int[] twoSum(int[] nums, int target) { int m=0,n=0,k,board=0; int[] res=new int[2]; int[] tmp1=new int[nums.length]; //备份原本下标的nums数组 System.arraycopy(nums,0,tmp1,0,nums.length); //将nums排序 Arrays.sort(nums); //双指针 for(int i=0,j=nums.length-1;i

账号		自动登录	找回密码
密码			立即注册