Day06–哈希表–242. 有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
Day06–哈希表–242. 有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
242. 有效的字母异位词
思路：
1、使用数组当哈希表，遍历第一个数组的时候加一，遍历第二个数组的时候减一，map全是0的时候返回true。
2、map的“hash”算法是[s.charAt(i) - ‘a’]。
class Solution { public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int n = s.length(); int[] map = new int[26]; for (int i = 0; i < n; i++) { map[s.charAt(i) - \'a\']++; } for (int i = 0; i < n; i++) { map[t.charAt(i) - \'a\']--; } for (int i = 0; i < 26; i++) { if (map[i] != 0) { return false; } } return true; }}349. 两个数组的交集
思路：
1、因为要确保元素是唯一的，使用set去存放元素；
2、第一个数组直接遍历，第二个数组使用contains()进行判断；
3、将set转换成int[]，可以考虑stream方法
class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set = new HashSet<>(); Set<Integer> res = new HashSet<>(); for (int i = 0; i < nums1.length; i++) { set.add(nums1[i]); } for (int i = 0; i < nums2.length; i++) { if (set.contains(nums2[i])) { res.add(nums2[i]); } } // 方法一：手动将set转成int[] int[] result = new int[res.size()]; int p = 0; for (int num : res) { result[p++] = num; } return result; // 方法二：使用stream转 // return res.stream().mapToInt(Integer::intValue).toArray(); }}其他题解：用数组做map
class Solution { public int[] intersection(int[] nums1, int[] nums2) { // 用数组做map int[] map1 = new int[1001]; int[] map2 = new int[1001]; List<Integer> list = new LinkedList<>(); for (int i = 0; i < nums1.length; i++) { map1[nums1[i]]++; } for (int i = 0; i < nums2.length; i++) { map2[nums2[i]]++; } for (int i = 0; i < 1001; i++) { int tem = Math.min(map1[i], map2[i]); if (tem != 0) { list.add(i); } } return list.stream().mapToInt(Integer::intValue).toArray(); }}202. 快乐数
思路：
1，注意关键词“无限循环”，意思就是，如果不变成1的话，会在某个数值循环，这时候就要想到去重哈希表，也就是set
2，熟练掌握，对数字分解，对每位数字进行操作。%10就是取末位，/10就是去掉末位。
class Solution { public boolean isHappy(int n) { Set<Integer> set = new HashSet<>(); while (n != 1 && !set.contains(n)) { set.add(n); n = getNextNum(n); } return 1 == n; } private int getNextNum(int num) { int sum = 0; while (num > 0) { int temp = num % 10; sum += temp * temp; num /= 10; } return sum; }}记录：自己做的时候，还真没想到，怎么退出循环的条件，还得是要仔细读题。然后，熟练练习分解数字的操作。
1. 两数之和
思路：
1，用map存“已经遍历过的元素和它的下标”，key是元素，value是下标。
2，每次存之前，先找map中有没有刚好和nums[i]凑成target的元素存在，也就是map.containsKey(target - nums[i])——注意，这里不能把map.put(nums[i], i);放在if前面，因为如果是[3,3]数组，target=6的话，就会出意外。
class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; int n = nums.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < n; i++) { if (map.containsKey(target - nums[i])) { res[0] = i; res[1] = map.get(target - nums[i]); } map.put(nums[i], i); } return res; }}记录：做了一天做累了，这么简单的题都想不出来。这可是在哈希表单元啊，除了数组，set，还有什么，就是轮到用map了。——当要存一个键值对的时候，要想到map
拓展题
49. 字母异位词分组
438. 找到字符串中所有字母异位词
350. 两个数组的交集 II
思路：和《一》是一样的，只不过，因为这次可以重复出现了，要用list装。
class Solution { public int[] intersect(int[] nums1, int[] nums2) { // 用数组做map int[] map1 = new int[1001]; int[] map2 = new int[1001]; List<Integer> list = new LinkedList<>(); for (int i = 0; i < nums1.length; i++) { map1[nums1[i]]++; } for (int i = 0; i < nums2.length; i++) { map2[nums2[i]]++; } for (int i = 0; i < 1001; i++) { int tem = Math.min(map1[i], map2[i]); if (tem != 0) { while (tem-- > 0) { list.add(i); } } } return list.stream().mapToInt(Integer::intValue).toArray(); }}对比下面《一》的代码，可以看到，《一》的呢，遇到>0的，就加一次就行；《二》这道题，就是要加n次。
class Solution { public int[] intersect(int[] nums1, int[] nums2) { // 用数组做map int[] map1 = new int[1001]; int[] map2 = new int[1001]; List<Integer> list = new LinkedList<>(); for (int i = 0; i < nums1.length; i++) { map1[nums1[i]]++; } for (int i = 0; i < nums2.length; i++) { map2[nums2[i]]++; } for (int i = 0; i < 1001; i++) { int tem = Math.min(map1[i], map2[i]); if (tem != 0) { list.add(i); } } return list.stream().mapToInt(Integer::intValue).toArray(); }}
