代码随想录算法训练营Day6 | 242.有效的字母异位词 ●349. 两个数组的交集 ● 202. 快乐数● 1. 两数之和

基础：

1.哈希表是根据关键值进行直接访问的数据结构，时间复杂度是O(1)，也就是通过数组的索引下标，直接访问数组中的元素哈希表的作用就是用来快速判断一个元素是否出现在集合里。

2.常见的哈希结构：

• 数组
• set （集合）
• map (映射)

List, Set, Queue, Map 区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，“x” 代表 key，“y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

242.有效的字母异位数

题目：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

题目链接：242. 有效的字母异位词

卡哥的视频链接：学透哈希表，数组使用有技巧！Leetcode：242.有效的字母异位词

题目思路：创建一个数组，遍历两个字符串，遍历第一个字符串时，把出现的字符串的ASCII码求出来，减去“a”的ASCII码，并得出数值，并在相应的数组位置加一，遍历第二个数组的时候变成减一，如果数组中有不为零的元素，则说明两个字符串不是完全一样的，本题只要求两个字符串所包含的元素相同，顺序无所谓。

代码示例：

代码逻辑详解：

1. int []record = new int[26];：创建一个长度为26的整数数组 record，用于记录每个字母在字符串 s 中出现的次数。数组的下标表示字母的索引，例如 record[0] 对应字母 a 的出现次数，record[1] 对应字母 b 的出现次数，以此类推。

2. for (int i = 0; i < s.length(); i++) {...}：遍历字符串 s 中的每个字符，对 record 数组进行更新。具体来说，对于字符串 s 中的每个字符，将该字符转换为相对于字母 a 的偏移量，并将对应的 record 数组中的计数加一。

3. for (int i = 0; i < t.length(); i++) {...}：同样地，遍历字符串 t 中的每个字符，但这次是将对应的 record 数组中的计数减一。

4. for(int count:record) {...}：使用增强型 for 循环遍历 record 数组中的每个元素 count。如果存在任何一个元素不等于0，说明字符串 s 中的某些字符在字符串 t 中没有完全匹配，因此返回 false。

5. 如果上述循环结束后，没有返回 false，则说明字符串 s 和字符串 t 是字母异位词，返回 true。

这段代码利用了一个技巧，即通过一个数组来记录字符串中每个字母的出现次数。在遍历完两个字符串后，只需检查数组中的元素是否都为0，即可判断两个字符串是否为字母异位词。

leetcode提交记录：

小tips：

charAt(i) 函数 是获取字符串中i位置的字符

s.charAt(i) - 'a'求字母的ascii码之间的差值。

string.charAt(i) - '0'将其转换为整数。

循环条件得出字符串的长度时，length后面记得加括号！！

349. 两个数组的交集

题目：给定两个数组 nums1 和 nums2 ，返回 它们的 

交集

 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

题目链接：349. 两个数组的交集

卡哥的视频链接：学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集

题目思考：我们只需要找到相同的元素即可，所以重复的可以忽略，所以我们申请两个set集合，因为set集合中的元素不可以重复，申请两个set集合，把第一个数组中包含的元素录入set1，把同时包含在set1和数组2的元素录入set2，最后遍历输出set2集合中的元素即可

代码示例：

代码逻辑详解：

1. if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; }：首先，检查输入的数组是否为 null 或长度为 0。如果其中任何一个数组为空，则返回一个空数组，因为两个空数组的交集也是空。

2. Set set1 = new HashSet<>();：创建一个 HashSet 集合 set1，用于存储 nums1 数组中的元素。这样做是为了方便快速查找 nums2 数组中的元素是否存在于 nums1 中。

3. Set resSet = new HashSet<>();：创建一个 HashSet 集合 resSet，用于存储两个数组的交集。

4. for(int i : nums1) { set1.add(i); }：遍历 nums1 数组中的元素，将每个元素添加到 set1 集合中。由于集合中不允许重复元素，这样可以确保 set1 中不会包含重复元素。

5. for(int i : nums2) { if(set1.contains(i)) { resSet.add(i); } }：遍历 nums2 数组中的元素，对于每个元素，检查是否存在于 set1 集合中。如果存在，则将该元素添加到 resSet 集合中，这样 resSet 集合中存储的就是两个数组的交集。

6. int[] arr = new int[resSet.size()];：创建一个数组 arr，其长度为 resSet 集合的大小，这样数组的长度就是交集的大小。

7. int j = 0; for(int i : resSet) { arr[j] = i; j++; }：遍历 resSet 集合中的元素，并将每个元素存储到数组 arr 中。这样，数组 arr 中存储的就是两个数组的交集。

8. return arr;：返回存储交集元素的数组 arr。

leetcode提交记录：

小tips：

得出集合长度是size而不是length

202.快乐数

题目：

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

题目链接：202.快乐数

此题卡哥无视频讲解

快乐数示例：

输入：19
输出：true
解释：

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

题目思考：编写求快乐数的函数，当所要求的数字不是一，也不重复时，就调用函数，计算出是否是快乐数

代码示例：

代码逻辑详解：

1. Set a = new HashSet<>();：创建一个 HashSet 集合 a，用于存储出现过的数字。这样做是为了检测循环，如果在循环中出现了重复的数字，就说明这个数不是快乐数。

2. while (n != 1 && !a.contains(n)) { ... }：使用 while 循环，循环条件是当 n 不等于 1 且集合 a 中不包含当前数字 n 时执行循环。这个循环会持续直到 n 变为 1（即快乐数）或者出现了重复的数字（即非快乐数）。

3. a.add(n);：将当前数字 n 加入到集合 a 中，标记为已经访问过。

4. n = getNextNumber(n);：调用 getNextNumber(n) 方法，根据当前数字 n 计算下一个数字，并将其赋值给 n。

5. public int getNextNumber(int n) { ... }：定义了一个方法 getNextNumber(int n)，用于计算下一个数字。在这个方法中，首先将 n 的各个位上的数字平方后相加，然后返回这个结果。

6. return n == 1;：如果循环结束后，n 等于 1，则说明这个数是快乐数，返回 true；否则，返回 false。

通过这段代码，可以判断一个整数是否是快乐数。如果一个数是快乐数，那么经过一系列计算后会得到 1；如果不是快乐数，会进入一个循环，最终导致计算出现重复的数字。

leetcode提交记录：

小tips：注意循环的条件！还有HashSet的写法

1.两数之和

题目：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

题目链接：1. 两数之和

卡哥的视频链接：梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！

题目思考：因为我们要进行查询，所以我们会想到用哈希表，因为我们需要同时储存两个量：元素和元素下标，所以我们使用map比较合适。

接下来需要明确两点：

• map用来做什么
• map中key和value分别表示什么

map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

接下来是map中key和value分别表示什么。

这道题 我们需要 给出一个元素，判断这个元素是否出现过，如果出现过，返回这个元素的下标。

那么判断元素是否出现，这个元素就要作为key，所以数组中的元素作为key，有key对应的就是value，value用来存下标。

所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

过程如图：

代码示例：

代码逻辑详解：

1. int [] res = new int[2];：创建一个长度为2的整数数组 res，用于存储找到的两个数的索引。

2. if(nums == null || nums.length == 0){ return res; }：首先，检查输入的数组 nums 是否为空或长度为0。如果是，则直接返回数组 res，因为没有任何元素可以计算。

3. Map map = new HashMap<>();：创建一个 HashMap 集合 map，用于存储数组中每个元素的值和对应的索引。

4. for (int i = 0; i < nums.length; i++) { ... }：遍历数组 nums 中的每个元素。

5. int temp = target - nums[i];：计算目标值 target 与当前数组元素 nums[i] 的差值，用 temp 变量存储。

6. if(map.containsKey(temp)) { ... }：检查 map 集合中是否包含差值 temp。如果包含，则说明找到了两个数的和等于目标值 target，进入下一步处理。

7. res[1] = i; 和 res[0] = map.get(temp);：将找到的两个数的索引分别存储到数组 res 中。由于 temp 是差值，而 i 是当前元素的索引，因此将 temp 的索引存储到 res[0] 中，当前元素的索引 i 存储到 res[1] 中。

8. break;：找到符合条件的两个数后，立即退出循环。

9. map.put(nums[i], i);：将当前元素 nums[i] 作为键，当前元素的索引 i 作为值，存储到 map 集合中。这样做是为了后续能够快速查找与当前元素相匹配的另一个数。

10. return res;：返回存储着两个数索引的数组 res。

通过这段代码，可以在给定整数数组中查找两个数的和等于目标值的索引，并以数组的形式返回。

leetcode提交记录：

小tips：

1.注意包含键的那个方法：containsKey()中的k是大写

2.注意map中的key和value是用来干什么的

3.最后返回的是数组，要把键和值储存在数组中，并且找到了要及时退出