一、哈希表理论基础

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

什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

Java常见哈希表：

所有 Java 哈希表（Map 结构）都不允许重复键。如果插入相同键，新值会覆盖旧值。

只有 HashMap 和 LinkedHashMap 允许 null 键，但最多只允许 一个 null 键。

二、242. 有效的字母异位词

直接创两个无序哈希表比较，Java语法里的细节需要注意（犯的错误）：

1.Map不存储基本数据类型，只存对象。

2.字符串要toCharArray()成字符数组才能遍历字符

3.Map不能像数组一样直接用[ ]获取值，必须用.get(key)。

4.Map添加数据要用put()，Set用add()；Map用containsKey()， Set用contains()。

5.字符串长度用length(); 数组长度.length; 集合长度.size()。

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character,Integer> leters= new HashMap<>();
        for(Character letter : s.toCharArray() ){
            if(leters.containsKey(letter)){
                leters.put(letter,leters.get(letter)+1);
            } else{
                leters.put(letter, 1);
            }
        }
        Map<Character,Integer> leters2= new HashMap<>();
        for(Character letter : t.toCharArray() ){
            if(leters2.containsKey(letter)){
                leters2.put(letter,leters2.get(letter)+1);
            } else{
                leters2.put(letter, 1);
            }
        }

        if(leters.equals(leters2) ){
            return true;
        }
        return false;
    }
}

优化1：只用一个哈希表，遍历value--，到0删除字母key，最后判断表为空返回true表明相同。

优化2：只含有小写字母可以直接用数组当哈希表

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

三、349. 两个数组的交集

元素唯一且无序，直接用set

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> sets = new HashSet<>();
        for(int num : nums1) { sets.add(num);}
        Set<Integer> common = new HashSet<>();
        for(int num: nums2) {
            if(sets.contains(num)) common.add(num);
        }
        return common.stream().mapToInt(Integer::intValue).toArray();
    }
}

Set转数组的方法：

1.集合——>对象流——>基本类型流——>基本类型数组

//x -> x 直接返回 int，等价于 Integer::intValue
IntStream intStream = stream.mapToInt(x -> x); // 直接返回 x

在 Java 8 中，Stream<Integer> 是 Java Stream API 提供的一种 流（Stream），用于处理 Integer 类型 数据序列。

关键点：

（1）Stream<Integer> 是 Stream 的泛型形式，表示流中存储的是 Integer 类型的元素。

（2）不是 数据结构，而是一种 数据流（pipeline），可以执行批量操作（如 map()、filter()、                 collect() 等）。

（3）区别于集合（List<Integer> 或 Set<Integer>），Stream<Integer> 不存储数据，而是对数据           进行操作。

.mapToInt() 的作用 用于将 Stream<T> 转换为 IntStream（即 Integer → int）。 参数是一个函数 ToIntFunction<T>，用于指定如何将 T 转换为 int。

Integer::intValue 其实是 方法引用 的简写，我们也可以用 Lambda 表达式：

lambda表达式语法：

2.创建一个新的数组手动转换

// 手动转换 Set<Integer> -> int[]
        int[] result = new int[common.size()];
        int i = 0;
        for (Integer num : common) {
            result[i++] = num;
        }
        return result;

三、202. 快乐数  
 

首先要考虑循环终止条件，等它返回true一定会在非快乐数时候时间超限，所以重点在如何判断可以返回false。因为sum是一直要迭代用的，当sum出现重复时就没必要继续了。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> sets = new HashSet<>();
        int sum = 0;
        while(sum!=1){
            
            //更新sum为0重新求和
            sum = 0;
            while(n>0){
                sum+= (n%10)*(n%10);
                n = n/10;
            }

            if(sets.contains(sum)){return false;}
            else{ sets.add(sum);
            //更新n
                n = sum;}
        }
        return true;  
    }
}

Tips： 时间复杂度为O(logn) ：

内循环求和时间复杂度取决于n的位数，约次；

外循环条件sum！=1，即使 n 很大，经过平方和转换，最终会收敛到一个较小的值。最多只会访问 一小部分数（经验上 ≤ 243）

四、1. 两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> pre = new HashMap<>();
        for(int i =0; i<nums.length;i++){
            if(pre.containsKey(target - nums[i]))
                {return new int[]{pre.get(target - nums[i]),i};}
            else{pre.put(nums[i],i);}
        }
        return new int[]{};
    }
}

用空间换时间，因为遍历和寻找的都是数组中的元素，可以把已经遍历过的元素存起来，减少寻找的时间开销。