2025-06-03 day7不day6的

哈希表

• 哈希表是为了快速的判断某一个元素是否在一个集合里的时候使用
• 关键码用哈希函数编码映射到索引上，使得快速找到，时间复杂度为O(1)
• 哈希碰撞，也就是同样的关键码会产生一样的编码，产生冲突
• 解决哈希碰撞的两种方法 1.拉链法 2.线性探测法
• 常见三种哈希结构：1.数组 2.set 3.map
• 牺牲空间来换取时间

242.有效的字母异位词

• 异位词：由相同个数的相同字母组成，例如abb和bab
• 视频讲解里使用的是，用数组来实现，很妙；数组也是一种哈希表

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] hash = new int[26]; //储存26个字母
        for(int i=0; i<s.length();i++) {
            hash[s.charAt(i) - 'a']++; //'a'就是char了，减去的话就是两个char的asii码的差值，char'a'就对应0
        }
        for(int i=0; i<t.length();i++) {
            hash[t.charAt(i) - 'a']--; //遇到相同的，直接--
        }
        for(int i=0;i<26;i++) {
            if(hash[i] != 0) {//不等于0，说明对应的字母个数有差距，不是异位词
                return false;
            }
        }
        return true; //说明都是0，是异位词
    }
}

• 真的是思路很重要啊
• 直接减去'a'字符，很妙。'a'就会对应数组中下标为0的元素。
• 学透哈希表，set使用有技巧！Leetcode：349. 两个数组的交集_哔哩哔哩_bilibili

349. 两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> resultSet = new HashSet<>();
        Set<Integer> nums1Set = new HashSet<>();
        for(int i:nums1){
            nums1Set.add(i);
        }
        for(int i:nums2) {
            if(nums1Set.contains(i)) { // 如果这个数字在nums1Set的话，add到resultSet
                resultSet.add(i);
            }
        }
        return resultSet.stream().mapToInt(Integer::intValue).toArray();
    }
}

• 可使用set和数组：数组可在数字较小时使用，set在数字大的时候。
• 使用set时，要把结果转换到int[]