哈希表
哈希表--有效的字母异位词
题目：力扣题目链接
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1: 输入: s = "anagram", t = "nagaram" 输出: true
示例 2: 输入: s = "rat", t = "car" 输出: false
说明: 你可以假设字符串只包含小写字母
题解：
class Solution {
public boolean isAnagram(String s, String t) {
int[] array= new int[26];
for(int i=0;i<s.length();i++){
array[s.charAt(i)-'a']++;
}
for(int j=0;j<t.length();j++){
array[t.charAt(j)-'a']--;
}
for(int count:array){
if(count!=0){
return false;
}
}
return true;
}
}
解析：
定义一个数组记录字符串s里字符出现的次数，如图所示，在通过t里的字符减少数组中字符出现的次数。
字符出现次数可用 array[s.charAt(i)-'a']++ 表示。字符减少次数可用 array[t.charAt(j)-'a']--表示
遍历完成后，如果数组中每一项都是出现0次，则是异位词，否则不是异位词。
哈希表--两个数组的交集
题目：力扣题目链接
给定两个数组，编写一个函数来计算它们的交集。
题解：
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1=new HashSet<>();
Set<Integer> set2=new HashSet<>();
for(int i:nums1){
set1.add(i);
}
for(int j:nums2){
if(set1.contains(j)){
set2.add(j);
}
}
int[] arr=new int[set2.size()];
int n=0;
for(int m:set2){
arr[n++]=m;
}
return arr;
}
}
解析：定义两个set集合，把num1的元素遍历出来装入set1，把num2的元素遍历出来，如果set1里面包含这个元素，则把该元素装进set2。直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。而且返回值是数组，所以new一个新数组用来装入set2元素。返回该新数组即可。
哈希表--快乐数
题目：力扣题目链接
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
输入：n = 2
输出：false
题解：
class Solution {
private int getNext(int n){
int result=0;
while(n>0){
int a=n%10;
n=n/10;
result+=a*a;
}
return result;
}
public boolean isHappy(int n) {
Set<Integer> set=new HashSet<>();
while(n!=1&&!set.contains(n)){
set.add(n);
n=getNext(n);
}
return n==1;
}
}
解析：1.n%10即可得个位数， n=n/10即把十位数变为个位数，执行getNext方法即可得下一个n
2.new一个HashSet集合，当n!=1并且n不为无限循环数即HashSet集合不包含该n时，把该n加入set集合中，然后调用函数获取下一个n值，直到n==1，跳出循环，返回true。否则若n在set集合中，即无限循环，返回false。
哈希表--两数之和
题目：力扣题目链接
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题解：暴力解法：
class Solution {
public int[] twoSum(int[] nums, int target) {
int n=nums.length;
Set<Integer> set =new HashSet<>();
int[] result=new int[2];
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(nums[i]+nums[j]==target){
set.add(i);
set.add(j);
}
}
}
int m=0;
for(int i : set){
result[m++]=i;
}
return result;
}
}
解析：
如图所示，不重复的遍历，使两数相加，若结果为目标值则把该值装进set集合里面，最后把set集合中的元素放到一个数组里面返回即可。由于时间复杂度高所以推荐使用哈希表法。
题解：哈希表法：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result=new int[2];
if(result==null||result.length==0){
return result;
}
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int t=target-nums[i];
if(map.containsKey(t)){
result[0]=map.get(t);
result[1]=i;
break;
}
map.put(nums[i],i);
}
return result;
}
}
解析：map集合可以用来存储我们存放过的元素，只有这样才能找到与当前元素相匹配的。
我们从数组头开始遍历，因为如果把该数组值做为map的value的话，根据map的value获取数组的下标相对麻烦。所以我们把该值做为map的key，把数组的下标做为map的value较为方便
target-nums[i]可以得到我们需要的值t，
如果map的key中包含该数组值，那么我们根据map.get(t)得到数组的下标放入新数组里面，把该下标i也放入新数组里面，break退出循环。
如果map的key中不包含该数组值，则就把访问过的元素和下标加入到map中，不断遍历即可。
最后返回新数组。
哈希表--四数相加II
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
- (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2：
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
题解：
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> map=new HashMap<>();
int t;
int result=0;
//统计两个数组中元素之和，map键为两数之和，值为出现的次数
for(int i:nums1){
for(int j:nums2){
t=i+j;
if(map.containsKey(t)){
map.put(t,map.get(t)+1);
}else{
map.put(t,1);
}
}
}
//统计剩余两个数组中两个元素的和，如果map中包含键为0-t，则将值相加，进行统计次数
for(int i:nums3){
for(int j:nums4){
t=i+j;
if(map.containsKey(0-t)){
result+=map.get(0-t);
}
}
}
return result;
}
}
解析：
- 四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以把四个数组两两统计，使得时间复杂度最小
- 需要一个map集合，key为两数之和，value为出现的次数
- 两个for循环遍历前两个数组，让两数相加得到t，如果map集合中包含该t，则让该t的出现次数也就是value值+1，不包含则把t加入map中，不断遍历。
- 让第三个数组和第四个进行for循环遍历，如果发现0-t在map的key中，则匹配成功，不断遍历和相加得出结果。
哈希表--赎金信
题目：力扣题目链接
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
示例 2：
输入：ransomNote = "aa", magazine = "ab"
输出：false
示例 3：
输入：ransomNote = "aa", magazine = "aab"
输出：true
题解：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] record=new int[26];
for(char c:magazine.toCharArray()){
record[c-'a']+=1;
}
for(char c:ransomNote.toCharArray()){
record[c-'a']-=1;
}
for(int a:record){
if(a<0){
return false;
}
}
return true;
}
}
解析：
- 定义一个数组，里面放26个字母出现的次数
- 把 magazine转化为一个字符串数组遍历出来每一个字符，对这个字符，让数组c-'a'处的值+1
- 把 ransomNote转化为一个字符串数组遍历出来每一个字符，对这个字符，让数组c-'a'处的值-1
- 遍历出该数组，查看字母出现的次数，如果出现<0的值则为false，若没有出现<0的值，则为true
哈希表--三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
题解：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]>0){
return result;
}
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int left=i+1;
int right=nums.length-1;
while(right>left){
int sum=nums[i]+nums[left]+nums[right];
if(sum>0){
right--;
}else if(sum<0){
left++;
}else{
result.add(Arrays.asList(nums[i],nums[left],nums[right]));
right--;
left++;
while(right>left&&nums[right]==nums[right-1]){
right--;
}
while(right>left&&nums[left]==nums[left+1]){
left++;
}
}
}
}
return result;
}
}
解析：双指针法：
-
用list集合对数组进行排序
-
定义三个指针，一个在头节点，一个left指针在其后，最后是一个right在数组的最后位置。
-
如果num[i]大于0，直接返回。细节是要对第一个指针进行去重操作
去重方法：
if(i>0&&nums[i]==nums[i-1]){ continue; }如果我们去重写成如下这样，则可能丢失一对正确的数据， 例如{-1, -1 ,2} 这组数据
if (nums[i] == nums[i + 1]) { // 去重操作 continue; } -
while(right>left)进行判断，如果sum>0,right--,若sum<0,left++;如果都不是则我们找到正确的值，把它加入到list集合里面，然后继续遍历让right指针左移，让left指针右移进行判断。细节是要对第二个指针，第三个指针进行去重操作。
去重方法：
前提right>left并且只要right指针的值和right-1的值相等时，让right左移。
前提right>left并且只要left指针的值和left+1的值相等时，让left右移。
哈希表--四数之和
题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
题解：
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
//减少时间复杂度，进行剪枝
if(nums[i]>0&&nums[i]>target){
return result;
}
//对nums[i]去重
if(i>0&&nums[i-1]==nums[i]){
continue;
}
for(int j=i+1;j<nums.length;j++){
if(j>i+1&&nums[j-1]==nums[j]){
continue;
}
int left=j+1;
int right=nums.length-1;
while(right>left){
long sum=(long)nums[i]+nums[j]+nums[left]+nums[right];
if(sum>target){
right--;
}else if(sum<target){
left++;
}else{
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
}
解析：双指针法：
-
用list集合对数组进行排序
-
用四个指针，一个在头节点，一个在其后，另一个left指针又在其后，最后一个right在数组的最后位置。
-
为了减少时间复杂度， 进行剪枝操作
if(nums[i]>0&&nums[i]>target){ return result; }-
对第一个指针进行去重操作，去重方法：
if(i>0&&nums[i-1]==nums[i]){ continue; }
5.对第二个指针进行去重操作，去重方法：
-
if(j>i+1&&nums[j-1]==nums[j]){
continue;
}
6.接下来和三数求和相同，见三数求和。
