🐟 4.两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。（好像还没见过那么短的题目）
题目链接：两个数组的交集https://leetcode-cn.com/problems/intersection-of-two-arrays/
题目分析：比较直接的方法是遍历nums1，对于它的每一个元素，在遍历nums2的时候判断该元素是否在数组nums2中。这里我们才用两个Set集合，哈希查询元素的效率是O(1)，可以帮助我们降低时间复杂度。
方法1：利用HashSet
时间复杂度O(n):n为nums1和num2的长度更长的那个，主要是用与两数组的遍历。
空间复杂度O(n)：n是num1的长度，最坏的情况下整个nums1都被装入到set中。
class Solution { public int[] intersection(int[] nums1, int[] nums2) { int n1=nums1.length; int n2=nums2.length; //用来存放其中一个数组 Set set=new HashSet(); //答案的长度不会超过短数组的长度 int[] arr=new int[Math.min(n1,n2)]; for(int i=0;i<n1;i++){ //set是不允许存放重复元素的，不用担心是否重复存入 set.add(nums1[i]); } //用来作为给答案数组放答案的指针 int j=0; for(int i=0;i<n2;i++){ //判断set中是否有，如果有说明两个数组都有 if(set.contains(nums2[i])){ //加入答案数组 arr[j++]=nums2[i]; //加入后就从set中去掉，防止nums2有重复的再次加入 set.remove(nums2[i]); } } //答案数组没有装满，就将后面减掉 return Arrays.copyOf(arr,j); } }
方法2：排序加双指针
为了获得数组的交集，我们可以将数组排序，然后利用两个指针分别指向两个数组的起始端，然后判断。如果相等，则加入进答案数组，在加入前需要判断是否已经加入过，然后两指针向右移动一位。
class Solution { public int[] intersection(int[] nums1, int[] nums2) { if(nums1==null||nums1.length==0||nums2==null||nums2.length==0){ return new int[0]; } //排序数组 Arrays.sort(nums1); Arrays.sort(nums2); int[] arr=new int[Math.min(nums1.length,nums2.length)]; //双指针 int p1=0; int p2=0; //用来放入答案数组的指针 int index=0; while(p1<nums1.length&&p2<nums2.length){ if(nums1[p1]==nums2[p2]){ //确保答案不重复 if(index==0||nums1[p1]!=arr[index-1]){ arr[index++]=nums1[p1]; } //无论是否放入数组，都应该++ p1++; p2++; }else if(nums1[p1]>nums2[p2]){ p2++; }else{ p1++; } } return Arrays.copyOfRange(arr,0,index); } }
🐳5.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。
题目链接：快乐数https://leetcode-cn.com/problems/happy-number/
题目分析：我们可以猜想，如果一个数字如果不是快乐数，那它在进行题目要求的操作时一定会有循环，也就是会产生重复数字。这是一个猜想，但也确实如此，它的证明是需要数学来证明的，但是这个猜想其实也很容易想到。一直循环下去肯定会出现重复数字导致循环。这样我们就可以利用HashSet来判断重复。
方法1：哈希检测循环
时间复杂度O(logn)：这道题目时间复杂度不好分析，因为我们不知道循环会多少次，无法去准备计算，大家了解是O(logn)即可
空间复杂度O(logn)：同理于上
class Solution { public boolean isHappy(int n) { //用来存储每次操作以后的数 Set<Integer> set=new HashSet<>(); //先将n放入 set.add(n); //一直循环，哈希检测 while(true){ //x保存n操作以后的值 int x=test(n); //说明是快乐数 if(x==1){ return true; } //未出现的数，放入set if(!set.contains(x)){ set.add(x); //出现过的数，说明不是快乐数 }else{ return false; } //把x赋值回给n n=x; } } //写一个操作方法 public int test(int n){ int count=0; while(n!=0){ int a=n%10; count+=a*a; n=n/10; } return count; } }
🐋6.赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
题目链接：赎金信https://leetcode-cn.com/problems/ransom-note/
题目解析：这道题目和前面第一道题的做法基本一模一样，只不过要求有一点点变化，这里直接贴上代码，只在第一题上稍微改动一下即可
方法：数组哈希映射
时间复杂度O(n)：n为ransomNote和magazine更长的字符串的长度。主要是遍历的耗时
空间复杂度O(1)：常数级数组的消耗视为O(1)
class Solution { public boolean canConstruct(String ransomNote, String magazine) { int[] arr=new int[26]; for(int i=0;i<ransomNote.length();i++){ arr[ransomNote.charAt(i)-'a']--; } for(int i=0;i<magazine.length();i++){ arr[magazine.charAt(i)-'a']++; } for(int i=0;i<26;i++){ if(arr[i]<0){ //小于0说明不够 return false; } } return true; } }
🐬7.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题目链接：两数之和https://leetcode-cn.com/problems/two-sum/
题目分析：不能太经典的题目，我在几数之和系列中也详细讲解过，这里就只为大家贴上哈希的做法。
时间复杂度O(n)：n为nums的长度，主要是循环的耗时
空间复杂度O(n)：n为nums的长度，主要是哈希的开销
class Solution { public int[] twoSum(int[] nums, int target) { int n=nums.length; //key存放值，value存放下标 Map<Integer,Integer> map=new HashMap<>(); for(int i=0;i<n;i++){ //找到了 if(map.containsKey(target-nums[i])){ //返回下标 return new int[]{map.get(target-nums[i]),i}; } //没找到放入map中 map.put(nums[i],i); } //遍历结束仍然未找到 return new int[0]; } }
☀️ 3.哈希总结（题目总链接）
哈希做法是经典的以空间换时间，我们做题一般都是更容易超时，哈希可以很好的帮我们解决这个问题。但是基础的题目只用哈希就可以，如果进阶的题目还需要和其他做法，比如双指针等等一起搭配。所以大家一定要打好哈希的基础，从简单题入手，不然以后用哈希都想不到。后续我也会写出哈希的进阶以及多种算法练习的练题集锦，希望大家收藏支持一下。
1.存在重复元素 https://leetcode-cn.com/problems/contains-duplicate/
2.存在重复元素|| https://leetcode-cn.com/problems/contains-duplicate-ii/
3.有效字母异位词 https://leetcode-cn.com/problems/valid-anagram/
4.两个数组的交集 https://leetcode-cn.com/problems/intersection-of-two-arrays/
5.快乐数 https://leetcode-cn.com/problems/happy-number/
6.赎金信 https://leetcode-cn.com/problems/ransom-note/
7.两数之和 https://leetcode-cn.com/problems/two-sum/
