哈希表开始 代码随想录训练营第6天

代码随想录训练营第6天

今日任务

●??哈希表理论基础

●??242.有效的字母异位词

●??349.?两个数组的交集

●??202.?快乐数

●??1.?两数之和

1.哈希表理论基础

了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set?和map。

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。??这句话很重要，大家在

文章讲解：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

2.242.有效的字母异位词

242.?有效的字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        //判断一个元素是否在什么中，考虑用哈希表法
        //将第一个数组元素通过你哈希值，转成索引，保存在哈希表中
        //将第二个数组元素通过哈希值得到索引，检查包不包含在哈爱惜表中，有就把它删掉，然后如果遍历哈希表得到值为0的话，那么就证明字母都是一样的

        //哈希表已经是封装定义好的，直接拿来用就行
        //比如说数值容量小的用数组,容量大用set,有value key我们用map
        //这里是字母字符串，只有26个字母，那我i们就用数组，数组元素都默认是0
        //先定义一个容量为26的数组，用来统计每一个字符串里面字母出现的频率，出现就在元素里面+1
        int[] hash=new int[26];
        for(int i=0;i<s.length();i++){
            //字符串包含 unicode 字符怎么办，用当前的字符减去字母第一个a，如果是a-a的话，最终a就在下标0的位置
            hash[s.charAt(i)-'a']++;
        }
        //遍历第二个字符串
        for(int i=0;i<t.length();i++){
            hash[t.charAt(i)-'a']--;
        }//将出现在同一个索引下标的元素减减

        //遍历hash数组，如果每个元素都是0，的话，证明两个字符串字母都是相同的
        for(int i=0;i<hash.length;i++){
            if(hash[i]!=0){return false;}
        }
        return true;
        //字符串的长度是方法，要用length()
        //数组的长度是属性，用.length
    }
}

3.?349.?两个数组的交集

349.?两个数组的交集

法一：数组

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //因为1 <= nums1.length, nums2.length <= 1000
        //先用数组解决
        int[] hash1=new int[1000];
        int[] hash2=new int[1000];

        //创建一个集合
        List<Integer> resList = new ArrayList<>(); 

        //遍历第一个刷组，将每一个元素出现的频率存储到哈希表中，并且值都给到1
        for(int i=0;i<nums1.length;i++){
            //hash1[nums1[i]%1000]++;
            hash1[nums1[i]]=1;
        }
        //遍历第二个数组,查看第二个数组的值在哈希表中位置的值是否等于1，如果等于1，证明是交集，那么我们存储到新的集合中（可以去重）
        for(int i=0;i<nums2.length;i++){
            if(hash1[nums2[i]]==1){
                //证明是交集
                resList.add(nums2[i]);
            }
        }
        //转为HashSet进行去重
        HashSet<Integer> set = new HashSet<>(resList);
         return set.stream().mapToInt(x->x).toArray();
        //遍历这些数值

    }
}

法二：Set

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        //用HashSet解决
        Set<Integer> hashSet1=new HashSet<>();
        Set<Integer> hashSet2=new HashSet<>();
        //将两个数组的元素存进哈希表中
        //这里遍历用for(int num:nums){输出num},这里的num就是每一个元素的值，而不是下标
        for(int num:nums1){
            hashSet1.add(num);
        }
        //判断数组2中的元素是否在1中包含过，如果包含过，则存进哈希表中
        for(int num:nums2){
            if(hashSet1.contains(num)){
                hashSet2.add(num);
            }
        }
        //那现在hashSet2就是存储着两个数组的交集了，HashSet也已经帮我们去重过了
        //直接将set转为数组就好
        return hashSet2.stream().mapToInt(x->x).toArray();
    }
}

4.202.?快乐数

202.?快乐数

class Solution {
    public boolean isHappy(int n) {
        //判断一个数是不是什么，优先考虑到哈希
        Set<Integer> hashSet1=new HashSet<>();
        while(n!=1&&!hashSet1.contains(n)){
            //如果结果不是1，那就把元素添加进哈希表中
            hashSet1.add(n);
            //继续去算每个位置上的数字的平方和
            n=getNextNumber(n);
        }
        //如果和为1，那么就证明是快乐数
        return n==1;
    }

    //求出每个位置的值，存进哈希表中
        //如果result是大于1，就继续重复这一段（写成一个函数）
        private int getNextNumber(int n){//每个位置上的数字的平方和
            int result=0;
            while(n>0){
                //取个位数
                int temp=n%10;
                result+=temp*temp;
                //舍去最后一位
                n=n/10;
            }
            return result;
        }
}

5.1.?两数之和

1.?两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //请你在该数组中找出 和为目标值 target  的那 两个 整数
        //考虑用到哈希

        //我们用哈希表来存放我们遍历过的元素（元素值和下标）
        //因为要找元素值和下标，所以我们考虑用哈希的map结构来存储
        Map<Integer,Integer> hashmap=new HashMap<>();
        
        //存放
        int[] arr=new int[2];

        if(nums == null || nums.length == 0){
            return arr;
        }

        //我们遍历元素，遍历第一个元素的时候，就要想当前target-当前元素的值是否在map集合中出现过，如果出现过，就证明我们找到了
        //如果没出现过，就继续往下遍历
        for(int i=0;i<nums.length;i++){
            int s=target-nums[i];
            if(hashmap.containsKey(s)){
                arr[0]=hashmap.get(s);
                arr[1]=i;
                break;
            }
                //往map里面存
                hashmap.put(nums[i],i);
        }
        //遍历完了
        return arr;
    }
}