[数据结构与算法]DAY6|242.有效的字母异位词 、 349. 两个数组的交集、202. 快乐数、1. 两数之和

什么时候想到用哈希法**，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法**。 这句话很重要，大家在做哈希表题目都要思考这句话。

直白来讲其实数组就是一张哈希表
那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。



**Java中的hash结构总结：HashSet、HashMap、HashTable:**https://blog.csdn.net/qq_34332616/article/details/114692538

242.有效的字母异位词
对字符串的操作要熟练
charAt
s.length()

class Solution {
    public boolean isAnagram(String s, String t) {
        //此题中哈希表用数组
        int[] hash=new int[26];
        for(int i=0;i<s.length();i++){
            hash[s.charAt(i)-'a']++;//s.charAt
        }
        for(int i=0;i<t.length();i++){
            hash[t.charAt(i)-'a']--;
        }
        for(int count:hash){
            if(count!=0){
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集
     hashSet 用add()添加元素 Set有去重效果 contains() size()

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //此题用set
        Set<Integer> set1=new HashSet<>();
        Set<Integer> res=new HashSet<>();
        for(int i:nums1){
            set1.add(i);
        }
        for(int i:nums2){
            if(set1.contains(i)){
                res.add(i);
            }
        }
        int[] array=new int[res.size()];
        int index=0;
        for(int i:res){
            array[index]=i;
            index++;
        }
        return array;
    }
}

202. 快乐数

class Solution {
    //用set方法
    public boolean isHappy(int n) {
        Set<Integer> res=new HashSet<>();
        while(!res.contains(n)){
            res.add(n);
            n=getNewNumber(n);
        }
        return n==1;
    }
    public int getNewNumber(int n){
        int res=0;
        while(n>0){//在去到最后一个数时 n/10=0不再进行
            int temp=n%10;//取最后一个数
            res+=temp*temp;
            n=n/10;//在划死最后一个数
        }
        return res;
    }
}

1. 两数之和
   
   get() 方法获取指定 key 对应对 value。
   put()

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //用map
        int[] res = new int[2];
        Map<Integer,Integer> map=new HashMap<>();//存放遍历过的元素 因为是查找元素 所以元素作为key 下标作为velue
        for(int i=0;i<nums.length;i++){
            int search=target-nums[i];
            if(map.containsKey(search)){
                res[0]=i;//结果要求放回下标
                res[1]=map.get(search);
                return res;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}