代码随想录二刷 Day05 | 242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和，454.四数相加II，383. 赎金信

题目与题解

参考资料：哈希表理论基础

Tips：

• 一般哈希表都是用来快速判断一个元素是否出现集合里
• 哈希表生成原理：先通过哈希函数将变量映射为hashcode，如果二者hashcode相同，再通过哈希碰撞方法（拉链法，线性探测法）将新变量的hashcode放入链表或哈希表的其他空位中
• 常见哈希结构：数组，集合set，映射map

242.有效的字母异位词

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

代码随想录题解：​​​​​​​242.有效的字母异位词

解题思路

        翻译过来就是要判断两个字符串中各个字符的数量是否相同，首先排除两个字符串长度不相同的情况。当两个字符串长度相同时，统计它们字符的数量，最简单的做法就是同时遍历两个字符串，先用哈希表记录其中一个字符串中每个字符的数量，然后根据另一个字符串的当前的字符减去哈希表中相应字符对应的数量。最后判断哈希表中每个字符的数量是否正好都为0即可。

class Solution {public boolean isAnagram(String s, String t) {if(s.length() != t.length()) return false;int[] count = new int[26];for (int i = 0; i < s.length(); i++) {count[s.charAt(i) - 'a']++;count[t.charAt(i) - 'a']--;}for (int i = 0; i < count.length; i++) {if (count[i] != 0) return false;}return true;}
}

注意点

        因为这里只需要统计字符的数量，所以哈希表用数组足矣，效率更高。

349. 两个数组的交集

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

代码随想录题解：​​​​​​​349. 两个数组的交集

解题思路

        交集是个很典型的集合概念，所以这套题的哈希表用集合非常合适。

        一开始想直接求出两个数组对应的集合，然后再用集合自带的函数求出交集。但是凭空写的时候不知道怎么把数组直接转换为集合，也不知道求交集的函数，于是偷偷看了一眼答案。答案没有用现成函数，所以老老实实手写吧。

        首先遍历nums1，用集合set逐一加入nums1中的元素，得到nums1对应的集合。

        然后设置集合crossSet，遍历nums2，如果nums2的元素也在set中，说明该元素存在交集中，将其加入crossSet。最后遍历crossSet，将其存到数组中，返回数组即可。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set = new HashSet<>();for (int i = 0; i < nums1.length; i++) {set.add(nums1[i]);}Set<Integer> crossSet = new HashSet<>();for (int i = 0; i < nums2.length; i++) {if (set.contains(nums2[i])) {crossSet.add(nums2[i]);}}int[] res = new int[crossSet.size()];int i = 0;for (int item:crossSet) {res[i++] = item;}return res;}
}

注意点

        在Java中，求HashSet的交集可以使用removeAll()方法。这个方法会从当前集合中删除所有包含在指定集合的元素。交集操作完成后，当前集合只保留与指定集合共有的元素。

import java.util.HashSet;public class Main {public static void main(String[] args) {HashSet<Integer> set1 = new HashSet<>();HashSet<Integer> set2 = new HashSet<>();HashSet<Integer> intersection = new HashSet<>();// 填充集合set1.add(1);set1.add(2);set1.add(3);set2.add(2);set2.add(3);set2.add(4);// 交集操作intersection.addAll(set1);intersection.removeAll(set2);set1.removeAll(set2);// 输出结果System.out.println("set1: " + set1); // 会输出 []，因为set1已经被修改System.out.println("set2: " + set2); // 输出 [2, 3, 4]System.out.println("交集: " + intersection); // 输出 [2, 3]}
}

        另外注意一下hashset的用法，加入元素要用add，遍历可以用java for each循环得到所有元素。

        题目有加数字的范围在0-1000之间，这种情况可以用数组替代Set类型，提高效率。

202. 快乐数

题目链接：202. 快乐数

代码随想录题解：​​​​​​​202. 快乐数

解题思路

        这题主要分成两步来写，一步用于计算数字的每一位上的平方和sum，一步用于判断sum是进入了无限循环，还是满足了和为1的要求。判断sum进入循环与否的方式可以用哈希表来完成。

        初始化本轮用于计算的数字num=n，用set记录每一次计算得到的平方和，当num不为1时，计算其每一位上的平方和，得到sum，如果sum不在set中，就把它加入set，否则说明已经出现了循环，该数不是快乐数。

class Solution {public boolean isHappy(int n) {Set<Integer> set = new HashSet<>();int num = n;set.add(num);while (num != 1) {int sum = 0;while (num != 0) {sum += (num%10)*(num%10);num /= 10;}if (set.contains(sum)) return false;else {set.add(sum);num = sum;}}return true;}
}

注意点

        计算平方和的时候，要注意用sum这个临时变量存储结果，当num不为0时，不断对其取余用来计算平方数加到sum上，取完余后不要忘记除以10，最后将sum赋值给num，用于下一轮的计算。

        set中判断元素是否存在用set.contains(element)即可。

1. 两数之和

题目链接：​​​​​​​1. 两数之和

代码随想录题解：​​​​​​​1. 两数之和

解题思路

        同一个元素不能使用两次，还需要查找元素，那最好遍历一次数组完成计算，既提高效率，又防止重复计算。

        用哈希表记录元素值及其对应的下标，但是这里有个小技巧，遍历时在哈希表中记录的不是当前元素值和其下标，而是target减去当前元素后的值和当前元素的下标，这样，往后遍历时，就可以直接通过containsKey判断当前元素是否在哈希表中，如果在，就直接得到前一个元素的下标和当前的下标，返回即可。

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i])) {return new int[]{map.get(nums[i]), i};} else {map.put(target - nums[i], i);}}return new int[2];}
}

注意点

        这题非常巧妙，用target-nums[i]一举两得，减少了搜索的时间，保留了需要的下标。

        同样注意一下hashmap的用法，加入元素用map.put(key, value)，判断元素是否存在用map.containsKey(key)。

454.四数相加II

题目链接：​​​​​​​454.四数相加II

代码随想录题解：​​​​​​​454.四数相加II

解题思路

        这题跟前一题思路有点类似，但更复杂一些，因为这里要求出所有符合条件的元组数量，不重复不遗漏。

        将四个数组分为两组，先用hashmap记录第一组数据分别有多少种不同的和(key)，每个和的数量是多少(value)，再遍历第二组数据，每次遍历计算-nums3[i]-nums4[j]，并判断它是否在前面的hashmap中，如果在，就把对应的value加入到结果的数量中。最后返回结果即可。

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer, Integer> sum1 = new HashMap<>();for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {sum1.put(nums1[i]+nums2[j], sum1.getOrDefault(nums1[i]+nums2[j], 0) + 1);}}int count = 0;for (int i = 0; i < nums3.length; i++) {for (int j = 0; j < nums4.length; j++) {int target = -nums3[i]-nums4[j];if (sum1.containsKey(target)) {count += sum1.get(target);}}}return count;}
}

注意点

        用hashmap统计数量的时候，可以用map.getOrDefault(key, 0)的方式，方便在map中找不到元素时就直接加入新元素并数量加一。

383. 赎金信

题目链接：​​​​​​​383. 赎金信

代码随想录题解：​​​​​​​383. 赎金信

解题思路

        这题跟有效字母异位词有点类似，不同之处在于magazine需要的字符数量需要包含ransomNote，而非字符数量相同。

        先用哈希表统计magazine中每个字符的数量，然后遍历ransomNote，在哈希表的基础上，每遍历到一个字符，就在相应字符的数量上减去1，最后统计哈希表中每个字符的数量是不是大于等于0即可。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {if (ransomNote.length() > magazine.length()) return false;Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < magazine.length(); i++) {map.put(magazine.charAt(i), map.getOrDefault(magazine.charAt(i), 0) + 1);}for (int i = 0; i < ransomNote.length(); i++) {char c = ransomNote.charAt(i);if (map.containsKey(c)) {int count = map.get(c) - 1;if (count < 0) return false;else map.put(c, count);} else {return false;}}return true;}
}

注意点

        这题其实也是统计字符数量，所以可以不用hashmap，直接用数组，效率会更高。

今日收获

        复习了一下哈希表的不同用法，数组、集合、映射类型的哈希表都写到了。哈希表常用于变量的数量统计，去重和用空间换时间的快速查找，这里要注意set和map一些对应的用法，不常写容易忘。