【随想录】Day6—第三章 哈希表part01

题目1：242.有效的字母异位词

• 题目链接：242. 有效的字母异位词

1- 思路

• 利用哈希表存储字符串 s 和字符串 t 中元素出现的频率，之后对比哈希表
• 本题采用数组的方式实现哈希表的存储

2- 题解

⭐有效的字母异位词 ——题解思路

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 i = 0 ;  i < t.length();i++){
            hash[t.charAt(i)-'a']--;
        }

        for(int n:hash){
            if(n!=0){
                return false;
            }
        }
        return true;
    }
}

题目2：349. 两个数组的交集

• 题目链接：349. 两个数组的交集

1- 思路

• 1. 利用一个 HashSet 来存储 数组中元素
• 2. 通过遍历 nums1 存入 其中元素，如果 遍历 nums 的过程中有相同的则 存入 res
• 3. 将 res 转为 int 数组返回

2- 题解

⭐两个数组的交集——题解思路

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> res = new HashSet<>();

        for(int n:nums1){
            set.add(n);
        }
        for(int n:nums2){
            if(set.contains(n)){
                res.add(n);
            }
        }

        int[] resNum = new int[res.size()];
        int index = 0;
        for(Integer r:res){
            resNum[index++] = r;
        }
        return resNum;

    }
}

题目3：202. 快乐数

• 题目链接：202. 快乐数

1- 思路

• 本题思路为，判断一个数是否为快乐数
• 根据题意可以知道，如果一个数在 不断求快乐数的过程中，出现了当前所求值 n 出现在 res 中，证明此时不是快乐术，因为出现了循环
• 如果 n == 1 ，证明找到了快乐数

因此思路如下

• 1. 定义主方法
• 通过 record 记录每次求快乐数的每一步，如果出现重复 跳出循环，如果 n == 1 跳出循环

public boolean isHappy(int n) {
    Set<Integer> record = new HashSet<>();
    while(n!=1 && !record.contains(n)){
        record.add(n);
        n = splitSum(n);
    }
    return n==1;
}

• 2. 定义对 n 快乐数拆分的方法
• 快乐数计算的步骤为：tmp = 最低位的平方 + 高位的平方
• 因此每次相当于对最低位计算即可，即 tmp%10
• 对当前 tmp 取余后 求平方 加上 上一次最低位的计算结果
• 每计算一次对 n/10 最 while 终止的条件为 n>0

private int splitSum(int n){
    int res = 0;
    while(n>0){
        int tmp = n % 10;

        res = tmp * tmp + res;
        n = n / 10;
    }
    return res;
}

2- 题解

⭐ 快乐数——题解思路

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while(n!=1 && !record.contains(n)){
            record.add(n);
            n = split(n);
        }
        return n==1;
    }

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

题目4：1. 两数之和

• 题目链接：1. 两数之和

1- 思路

• 哈希表求解——用 map 因为涉及到 nums 索引的返回
• 1. 先将 nums 中的值全存入 HashMap 中
  • key 为值
  • value 为下标
• 2. 遍历 nums ，判断 mpa 中是否存在 (target-nums[i]) 的 key 若存在则 通过 key 找到下标
• 3. 返回下标结果

2- 题解

⭐ 两数之和——题解思路

注：填充哈希表和查找目标值是在同一个循环中完成的。这意味着，一旦找到满足条件的一对数，就会立即返回它们的索引，而不会有覆盖问题。这种方法即使在面对重复元素时也能正确工作，因为它在添加元素到哈希表之前就进行了目标值的检查。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int[] res = new int[2];


        for(int i = 0 ; i < nums.length ;i++){
            if(map.containsKey(target-nums[i])){
                res[0] = i;
                res[1] = map.get(target-nums[i]);
            }
            map.put(nums[i],i);
        }
        return res;
    }
}