[数据结构与算法]代码随想录训练营day06， 哈希表：有效的字母异位词， 两个数组的交集， 快乐数， 两数之和

今天正式开始哈希算法的学习， 之前没有学过， 所以要花点时间在基本概念上， 注意数组就是简单的哈希表。

有效的字母异位词

总体思路：利用哈希表数组， 创建一个26位大小数组， 然后利用ascii码表将题目里的信息输入到table里， 一个用来++， 一个用来--， 最后判断table是否为0

（使用数组解的前提是题目限制了数组的大小）

新知识：

1. s.charAt(i)是用来返回字符串在i位置的值， 大小写看清楚

2.他这里用s.charAt - 'a'就会自动计算index数字， 所以table【xxx】++意思就是在第i个位置加1

细节：

1. 这里的‘a’必须要用单引号

2. 其实有三个for遍历， 第一个遍历加数字， 第二个遍历减数字， 第三个遍历用来判断table是否为0. 注意：要不等于0弹出false得写在里面

3. 当获得字符串的大小的时候要加括号 s.length()

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] result = new int[26];
        for(int i = 0; i < s.length(); i++ ){
            result[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < t.length(); i++ ){
            result[t.charAt(i) - 'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(result[i] != 0){
                return false;
            }
        }
        return true;
    }
}

两个数组的交集

总体思路：?遍历第一个然后全部转换为哈希表， 然后同样遍历第二个， 注意是去重， 如果之前出现过就放到result集合里（注意， 这里只要创建一个set1数组， 一个result set数组）

新知识：

1. 创建一个hashset需要如下： Set<Integer> set = new HashSet<>(); 注意大小写

2. 将结果集合转为数组：?return?resSet.stream().mapToInt(x?->?x).toArray();

补充细节：

增强for循环：

这里的循环时int i ：nums1， 也就是说i是数组nums1的一个元素

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for(int i : nums1){
            set1.add(i);
        }
        for(int i : nums2){
            if(set1.contains(i)){
                resSet.add(i);
            }
        }
        return resSet.stream().mapToInt(x -> x).toArray();
    }
}

普通循环：
这里的i是索引，所以里面加的内容都要变成nums[i]

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组一
        for(int i = 0; i < nums1.length; i++){
            set1.add(nums1[i]);
        }
        //遍历数组二， 用contain比较
        for(int i = 0; i < nums2.length; i++){
            if(set1.contains(nums2[i])){
                resSet.add(nums2[i]);
            }
        }
        return resSet.stream().mapToInt(x -> x).toArray();
    }
}

这个也可以使用数组解决， 但是限制太多， 所以就不多阐述了。

快乐数
思路总结:?分为两部分

第 1 部分我们按照题目的要求做数位分离，求平方和。

第 2 部分可以使用哈希集合完成。每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。

如果它不在哈希集合中，我们应该添加它。 如果它在哈希集合中，这意味着我们处于一个循环中，因此应该返回 false。

（我们使用哈希集合而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集合中需要 O(1)O(1) 的时间，而对于其他数据结构，则需要 O(n)O(n) 的时间）

细节：
1. 写一个方法getNext, 要先定义一个digit计算个位, 然后再定义一个十位数用 +=sum

2. 回到boolean方法, 定义哈希数组放入数据, 判断, n不为1, 同时没有重复的, 否则return

3.getNext方法是return sum, 这个sum就是新的n

class Solution {
    public boolean isHappy(int n) {
    //利用HashSet来确认是否有数组重复
        Set<Integer> hash =  new HashSet<>();
        while(n != 1 && !hash.contains(n)){
            hash.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    //创建求出个位平方和十位平方的和
    private int getNext(int n){
        int sum = 0;
        while(n > 0){
            int digit = n % 10;
            sum += digit*digit;
            n = n/10;
        }
     return sum;   
    }
}

容易理解版本:

死循环判断, 等于1, 或者进入循环了

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> arr = new HashSet<>();
        while(true){
            if(n == 1){
                return true;
            }
            if(arr.contains(n)){
                return false;
            }
            arr.add(n);
            n = getNext(n);
        }
    }
    public int getNext(int n){
        int sum = 0;
        while(n > 0 ){
            int digit = n % 10;
            sum += digit*digit;
            n = n/10;
        }
        return sum;
    }
}

两数之和

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要首先想到哈希法
总结思路:

temp = target - nums[i], 看temp是否存在哈希表中, 不存在则存入nums[i]和i, 循环, 直到temp存在于哈希表, 然后return temp的索引和这个数的索引

新知识:
1. 创建HashMap: Map<Integer, Integer> = new HashMap<>();

2.map的方法, map.containsKey(), map.put()

3.通过哈希表获得索引, map.get(temp)

细节:
1.创建一个HashMap

2.for遍历数组里所有的数, 然后判断, temp是否已经存在, 存在就直接return两个索引

3. 不存在就放到哈希表里面

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //创建一个哈希表
        Map<Integer, Integer> map =  new HashMap<>();
        //遍历判断
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            //如果temp已经存在于哈希表里了, 就return temp索引和当前索引
            if(map.containsKey(temp)){
                return new int[]{map.get(temp),i};
            }
            //如果不存在, 就放入哈希表
            map.put(nums[i],i);
        }
        //遍历完上面的都没有return, 那就直接返回0
        return new int[0];
    }
}