前言
哈希表(英文名 Hash table, 国内也被称为散列表)
哈希表是根据关键码的值而直接进行访问的数据结构, 数组就是一张哈希表
哈希表一般用来快速判断一个元素是否出现在集合里
例如要查询一个名字是否在这所学校里。
要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。
我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数
上述例子来源于代码随想录
今日任务：
咱就是说， 万万没想到我现在做曾经做过的简单题竟然这么的游刃有余，哈哈哈哈哈
242. 有效的字母异位词
题目描述
解题思路
整体解题思路就是记录字符串 s中每一个字母计算出现的次数， 再去遍历字符串 t中的每一个字母去做比较是否一致
字符串转 char数组 循环遍历 char数组使得对应下标 ++ 在 --， 如果当前下标出现 -的就代表元素个数不一致
最后一步的判断可以留到最后遍历我们的统计数组来做， 也会更快一点， 不用每一次对数组进行操作的时候都去判断
代码展示
public static boolean isAnagram(String s, String t) { if (s.length() != t.length()){ return false; } int[] intsS = new int[26]; char[] charsS = s.toCharArray(); for (int i = 0; i < charsS.length; i++) { intsS[charsS[i] - 'a'] = intsS[charsS[i] - 'a'] + 1; } char[] charsT = t.toCharArray(); for (int i = 0; i < charsT.length; i++) { intsS[charsT[i] - 'a'] = intsS[charsT[i] - 'a'] - 1; if (intsS[charsT[i] - 'a'] < 0){ return false; } } return true; } 复制代码
提交结果
总结
多学多练算法不一定会让你的编码水平变得多么高深，甚至在你工作中可能完全用不到，但是如果碰到了就是赚了
只能说游刃有余，虽然最后一步是在每次修改统计数组的时候去做的判断，增加了时间消耗，但是实际上在编码过程中考虑到了这个问题，只是懒得改了，大家不要有这个坏习惯
349. 两个数组的交集
题目描述
解题思路
和上一道题一样的，先去记录每一个元素是否出现过，如果出现过就加入到返回里面
需要注意的是要用 Set集合，因为元素是可能重复的
代码展示
public static int[] intersection(int[] nums1, int[] nums2) { Set<Integer> result = new HashSet<>(); Map<Integer,Integer> map = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1); } for (int i = 0; i < nums2.length; i++) { if (map.get(nums2[i]) != null) { result.add(nums2[i]); } } return result.stream().mapToInt(Integer::intValue).toArray(); } 复制代码
提交结果
202. 快乐数
题目描述
解题思路
这道题就是一直去按照题目中的要求计算， 然后用 Set去存储每一次计算出来的返回值，如果返回值已存在则证明陷入了死循环
代码展示
class Solution { public boolean isHappy(int n) { Set<Integer> set = new HashSet<>(); while(n != 1){ set.add(n); n = test(n); if (set.contains(n)) { return false; } } return true; } public int test(int n){ int result = 0; while(n >= 10){ int m = n % 10; n /= 10; result += m * m; } return result += n * n; } } 复制代码
提交结果
总结
这道题第一次提交的时候，在 test方法里面循环判断 >= 10 写成了 >10 边界没判断清楚， 失误失误
1. 两数之和
题目描述
解题思路
创建 map存储元素值和下标
遍历数组，判断 map中是否存在 （target - 当前元素），若存在，则直接返回两个下标， 若遍历结束都不存在则直接返回 null
代码展示
public static int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target - nums[i])) { return new int[]{i,map.get(target - nums[i])}; }else{ map.put(nums[i], i); } } return null; } 复制代码
提交结果
总结
万万没想到以前这道题还给我带来了这么大的困扰，竟然错过这么多次， 手动捂脸，哈哈哈，重新做起来真的是游刃有余
