哈希表理论基础
参考: 代码随想录 (programmercarl.com)
242.有效的字母异位词
题目链接: 242. 有效的字母异位词 - 力扣（LeetCode）
题目
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram" 输出: true
示例 2:
输入: s = "rat", t = "car" 输出: false
思路
方法一：暴力法:两层for循环，同时记录字符是否重复出现 。时间复杂度： O(n^2)。
方法二：利用数组做一个简单的哈希表。因为这道题目中字符串只有小写字符，所以可以定义一个数组，通过数组来记录字符串s里字符出现的次数。
因为只有小写字母，所以数组大小为26 (a - z)就可以了，初始化为0。时间复杂度：O(m + n)
注意:
- 可以通过该题感受一下 数组 用来做 哈希表 给我们带来的便利。
- 常用的三种哈希表有数组、set和map，当哈希表比较小并且范围确定的时候，用数组；当哈希表范围比较大而且不确定的时候，用set；当有key-value的映射关系的时候，用map。
- 数组就是简单的哈希表，但是数组的大小可不是无限开辟的。
代码
1 lass Solution {
2 public boolean isAnagram(String s, String t) {
3 int[] record = new int[26];
4
5 for (int i = 0; i < s.length(); i++) {
6 record[s.charAt(i) - 'a']++;
7 }
8
9 for (int i = 0; i < t.length(); i++) {
10 record[t.charAt(i) - 'a']--;
11 }
12
13 for (int count: record) {
14 // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
15 if (count != 0) {
16 return false;
17 }
18 }
19 // record数组所有元素都为零0，说明字符串s和t是字母异位词
20 return true;
21 }
22 }
349. 两个数组的交集
题目链接: 349. 两个数组的交集 - 力扣（LeetCode）
题目
给定两个数组 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] 也是可通过的
思路
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。由于该题没有限制数值的大小，就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。所以选择set是最优解。
使用set的思路如下：
- 首先，定义一个Set变量 resSet ，存放之后要返回的结果，之所以用set是因为它可以帮我们自动去重；
- 遍历nums1中的元素并存放到另一个哈希表 set1 中（去重操作）；
- 遍历nums2中的元素，然后在 set1 这个哈希表中是否包含该元素，如果包含的话，就把它存到 resSet 中去；
- 遍历结束之后，将resSet转换为数组返回
代码
1 class Solution {
2 public int[] intersection(int[] nums1, int[] nums2) {
3 if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
4 return new int[0];
5 }
6
7 Set<Integer> set1 = new HashSet<>();
8 Set<Integer> resSet = new HashSet<>();
9 // 遍历数组1
10 for(int i = 0;i < nums1.length;i++){
11 set1.add(nums1[i]);
12 }
13 // 遍历数组2的过程中判断哈希表中是否存在该元素
14 for(int i = 0;i < nums2.length;i++){
15 if(set1.contains(nums2[i])){
16 resSet.add(nums2[i]);
17 }
18 }
19 // 将结果转换为数组返回,也可简写
20 // return resSet.stream().mapToInt(x -> x).toArray();
21 int[] ans = new int[resSet.size()];
22 int i = 0;
23 for(Integer num : resSet){
24 ans[i++] = num;
25 }
26 return ans;
27 }
28 }
202. 快乐数
题目链接: 202. 快乐数 - 力扣（LeetCode）
题目
编写一个算法来判断一个数 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
思路
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！
为什么会一定会重复出现?
先来看每位数最大的情况
| 位数 | 位数的最大值 | 下一个数 |
| 1 | 9 | 81 |
| 2 | 99 | 162 |
| 3 | 999 | 243 |
| 4 | 9999 | 324 |
例如，三位数的下一个值不可能大于243，这就意味着当哈希表的243个数全部占完时，必备下一次就会造成哈希冲突，也就是出现重复值。
题目给的例子最大值为2^31 = 2,147,483,648，而十位数中最大值为 9999999999，它的下一个数为 810，刚好三位数，所以一定会出现重复值。
当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
代码
1 class Solution {
2 public boolean isHappy(int n) {
3 Set<Integer> record = new HashSet<>();
4 while (n != 1 && !record.contains(n)) {
5 record.add(n);
6 n = getNextNumber(n);
7 }
8 return n == 1;
9 }
10
11 private int getNextNumber(int n) {
12 int res = 0;
13 while (n > 0) {
14 int temp = n % 10;
15 res += temp * temp;
16 n = n / 10;
17 }
18 return res;
19 }
20 }
1. 两数之和
题目链接: 1. 两数之和 - 力扣（LeetCode）
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
思路
暴力法:两层for循环查找，时间复杂度: 是O(n^2)
哈希法: 使用一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否在该集合中。例如：遍历到第二个数，7的时候，我们需要查target-7=2，是否出现过。
重点
为什么会想到用哈希表 ?
当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
哈希表为什么用map?
因为我们不仅要知道元素有没有遍历过，还有知道这个元素对应的下标，需要使用 key-value结构来存放，key来存元素，value来存下标。
再来看一下使用数组和set来做哈希法的局限。
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
本题map是用来存什么的?
map用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下表，这样才能找到与当前元素相加等于 target 的数。
map中的key和value用来存什么的?
组中的元素作为key，有key对应的就是value，value用来存下标。
代码
1 public int[] twoSum(int[] nums, int target) {
2 int[] res = new int[2];
3 if(nums == null || nums.length == 0){
4 return res;
5 }
6 Map<Integer, Integer> map = new HashMap<>();
7 for(int i = 0; i < nums.length; i++){
8 int temp = target - nums[i]; // 遍历当前元素，并在map中寻找是否有匹配的key
9 if(map.containsKey(temp)){
10 res[1] = i;
11 res[0] = map.get(temp);
12 break;
13 }
14 map.put(nums[i], i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中
15 }
16 return res;
17 }
标签：map,202,哈希,nums,int,元素,随想录,数组,两数 From： https://www.cnblogs.com/xpp3/p/17100335.html