哈希表理论基础

文章讲解：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

知识点：
哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。

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

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

假设有一个包含 1000 个元素的 HashSet：
查找特定元素时，只需要计算哈希值并访问相应的桶，时间复杂度为 O(1)。
遍历所有元素时，需要访问 1000 次，每个元素都要访问一遍，时间复杂度为 O(n)。

242.有效的字母异位词

题目链接/文章讲解/视频讲解

解题思路：

• anagram：字母构成相同，顺序不同；完全相同的字符串也是valid anagram
• 刷题时想到hash问题基本就想到三种数据结构：数组，set，map
• 字符串都是由小写字母组成，它们的ASCII也是26个连续的数值，所以可以设定一个大小为26的数组hash，a对应数组下标为0的位置，以此类推。
• 用hash统计第一个字符串中每一个字母出现的频率，在遍历第二个字符串时，每个字母出现的频率在hash中做减法，如果return 0，就时valid anagram

数组、set、map使用的场合：

• 数组：哈希值较小，范围可控
• set：数值很大的时候
• map：key对应了value

pseudocode

if(s.length != t.length){
    return false;
}
int[] hash = new int[26];
for(i=0; i < s.length; i++){
    hash[s.charAt[i] - 'a']++; 
//计算出当前字符在 record 数组中的索引位置。
//例如，'a' - 'a' = 0, 'b' - 'a' = 1，以此类推。
}
for(i=0; i < t.length; i++){
    hash[s.charAt[i] - 'a']--;
}
for(int count : hash){
    if(count != 0){
    return false;
    }
}
return true;

出现的编译错误
数组或字符串的长度应该用.length()方法而不是.length属性。
s.length(这是数组的写法) 应改为 s.length()（这是字符串的写法）

字符串中字符的访问应该使用.charAt(index)方法，而不是.charAt[index]。
s.charAt[i] 应改为 s.charAt(i)

对语法还不熟练TT

349. 两个数组的交集

题目链接/文章讲解/视频讲解

建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set。

注意：返回的交集是去重的。
解题思路：nums1进行处理，转变为哈希表的形式，存储nums1中所有的元素；nums2再去遍历查询哈希表里是否出现过，如果出现过就放入result集合中。

选择set来解题：
Java中的set结构

pseudocode

//使用HashSet
        Set<Integer> resultSet = new HashSet<>(); // 存放结果，使用Set是为了去重
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums1) {
            numsSet.add(num);
        }
        
        for (int num : nums2) {
            if (numsSet.contains(num)) {
                resultSet.add(num);
            }
        }
        
        // 将结果集转换为数组
        int[] resultArray = new int[resultSet.size()];
        int index = 0;
        for (int num : resultSet) {
            resultArray[index++] = num;
        }
        
        return resultArray;
    }

或者

return resSet.stream().mapToInt(x -> x).toArray();

• resSet.stream():
  stream() 方法将集合转换为一个顺序流（Stream<Integer>）。Stream 是一种可以从集合中提取和操作数据的高级抽象。
• mapToInt(x -> x):
  mapToInt 是一个中间操作，它将流中的每个元素转换为一个 int 值，生成一个 IntStream（整数流）。
• x -> x 是一个 lambda 表达式，表示对于流中的每个元素 x，直接将其作为 int 返回。这里的 x 是流中的元素，x -> x 表示不做任何转换。
• toArray():
  toArray() 是一个终端操作，它将 IntStream 中的所有元素收集到一个新的 int[] 数组中。

使用数组解决：

        nt[] hash1 = new int[1002];
        int[] hash2 = new int[1002];
        for(int i : nums1)
            hash1[i]++;
        for(int i : nums2)
            hash2[i]++;
        List<Integer> resList = new ArrayList<>();
        for(int i = 0; i < 1002; i++)
            if(hash1[i] > 0 && hash2[i] > 0)
                resList.add(i);
        int index = 0;
        int res[] = new int[resList.size()];
        for(int i : resList)
            res[index++] = i;
        return res;

202. 快乐数

题目链接/文章讲解

sum重复出现，就肯定不是快乐数，为什么呢？
因为只要重复出现一次就说明会无限循环，就像之前链表那个环，假设a1算完等于a2,a2算完等于a3，a3算完等于a1，那么下一次a1算完必定等于a2，再下一次a2算完必定是a3，形成了一个循环，而这个循环中不可能有1，因为1平方的结果永远是1,所以肯定有循环就肯定不是快乐数，是快乐数就肯定没有循环

class Solution {
    public boolean isHappy(int n) {
        // 使用HashSet存储已经出现过的数字，检测循环
        Set<Integer> record = new HashSet<>();
        // 循环直到n为1或者n已出现过
        while(n != 1 && !record.contains(n)){
        // 记录当前数字
            record.add(n);
        // 计算下一个数字
            n = getNextNum(n);
        }
        // 如果n为1，则为快乐数
        return n == 1;
    }
       


        // getNextNum方法
    private int getNextNum(int n){
        // res用于存储每位平方的和
        int res = 0;
        // 当n大于0时继续处理
        while(n > 0){
        // 获取n的最低位
            int temp = n % 10;
        // 将最低位的平方加到结果中
            res += temp * temp;
        // 移除n的最低位
            n = n / 10;
        }
        // 返回计算后的新数字
        return res;

     }
        
    
}

1. 两数之和

题目链接/文章讲解/视频讲解

解题思路：

• 想到使用hash法：遇到判断元素是否在集合中出现过。
• 在遍历元素B时要判断之前是否遍历过和B相加等于target的元素A，如果之前遍历过，就找到了一对符合的数值。
• 因为既要知道元素存放的值又要知道存放的数组下标，所以使用Map。
• 为什么要用数值做key而不是下标做key？因为要查找元素是否出现过（Map的作用就是快速查找key）。

Java中的Map：

pseudocode

int[] res = new int[2];
if(nums == null || nums.length == 0){
        return res;
    }
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0;i<nums.length;i++){
    //遍历中寻找查询的值
    int s = target - nums[i];
    //如果找到了
    if(map.containsKey(s)){
        res[1] = i;
        res[0] = map.get(s);
        break;
    }
    //如果没找到，要把当前遍历的元素加入map
    map.put(nums[i],i);
}
return res;

自己写的时候，map.containsKey(s)方法不熟
res[0] = map.get(s); 想了很久拿到下标的方法
还要注意if语句中的break

• 这道题目的四个重点：
  为什么会想到用哈希表
  哈希表为什么用map
  本题map是用来存什么的
  map中的key和value用来存什么的