训练营day06：哈希表1

242.有效的字母异位词

https://leetcode.cn/problems/valid-anagram/description/
还是需要看思路的一道题，逻辑比较简单，若干年前用过这种解法已经忘了，需要复习下。
注：这道哈希题目用的是数组

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']++;
        }
        for(int j = 0; j < t.length(); j++) {
            hash[t.charAt(j) - 'a']--;
        }
        for(int count = 0; count < 26; count++) {
            if(hash[count] != 0) {
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集

https://leetcode.cn/problems/intersection-of-two-arrays/description/

// 1.set 数据结构解法
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resultSet = new HashSet<>();
        for(int value : nums1) {
            set1.add(value);
        }
        for(int value : nums2) {
            if(set1.contains(value)) {
                resultSet.add(value);
            }
        }

        int[] resultArray = new int[resultSet.size()];

        int i = 0;
        for (int value : resultSet) {
            resultArray[i++] = value;
        }

        return resultArray;
    }
}
// 2. 数组解法
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
    
        int kk = 100;
        int[] array1 = new int[1001];
        int[] array2 = new int[1001];

        int[] tmpArray = new int[1001];
        for (int value : nums1) {
            array1[value] = kk;
        }

        for (int value : nums2) {
            array2[value] = kk;
        }
        List<Integer> tmp = new ArrayList<>();
        for(int i = 0;i < 1001;i++) {
            if (array1[i] > 0 && array2[i] > 0) {
                tmp.add(i);
            }
        }
        // 最后需要输出int类型数组，List类型不行
        int total = tmp.size();
        int[] resultArray = new int[total];
        int i = 0;
        for (int value : tmp) {
            resultArray[i++] = value;
        }
        return resultArray;
    }
}

题后感：
大家说这道题简单，我哭了……虽然真的不复杂，但是hash相关题目还是不熟，解法没有链表熟悉，多多联系吧

202. 快乐数

https://leetcode.cn/problems/happy-number/
题目很简单，重点就是判断这个数会不会无限循环，用hashset判断

// 我的答案
import java.util.HashSet;
import java.util.Set;

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

        return false;
    }
}
// 卡哥答案还是更简洁一些，把计算下一个数的逻辑抽出来了
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}

1. 两数之和

https://leetcode.cn/problems/two-sum/
看到题只想到了暴力解法，先看了解法文字，本来以为解法是先将数组全部遍历一遍将值和下标放到hashmap中，然后再遍历数组，从hashmap找到对应值，卡哥给的解法是一次循环遍历搞定，如果hashmap没有值就将值放进去，完成全部遍历求解，时间复杂度和空间复杂度都是更优秀。
背下来！
另外记住java里hashmap存取常用方法：

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if (nums == null || nums.length == 0) {
            return res;
        }
        Map<Integer,Integer> temp = new HashMap<>();
        for (int i = 0;i < nums.length;i++) {
            int cur = nums[i];
            int toFind = target - cur;
            if (temp.containsKey(toFind)) {
                res[0] = i;
                res[1] = temp.get(toFind);
            } else {
                temp.put(cur, i);
            }
        }
        return res;
    }
}