第三章哈希表part01

242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

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

242.有效的字母异位词

注意点：字符串长度表示方法 s.length（）要带括号

　　　　字符串取字符 s.charAt(index)

　　　　ASCII码相减运算 'b' - 'a'

class Solution {
    public boolean isAnagram(String s, String t) {
        // 哈希法 数组实现
        // 记录数组，记录26个字母
        int record[] = new int[26];
        // s的每个字母出现的次数 ++
        for (int i = 0; i < s.length(); i++){
            record[s.charAt(i) - 'a']++;
        }
        // t的每个字母出现的次数 --
        for (int i = 0; i < t.length(); i++){
            record[t.charAt(i) - 'a']--;
        }
        // 看记录数组是否全0
        for (int count : record){
            if (count != 0){
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集

个人思路是延续上一题，用大小为1001的数组记录元素是否出现，但是去重问题解决不了。解决方案：额外记录变量 $pre表示上一次加入答案数组的元素$

用哈希set解决

注意点：不能用count计数结果元素去创建结果数组，还是去重问题，用ansSet.size()即可

创建哈希set的写法 Set<Integer> set = new HashSet<>()

　　　　哈希set判断是否包含元素i：set.contains(i)

　　　　哈希set添加元素i：set.add(i)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // 哈希set
        Set<Integer> set1 = new HashSet<>();
        // 结果
        Set<Integer> ansSet = new HashSet<>();
        // 遍历nums1
        for (int i : nums1){
            set1.add(i);
        }
        // 遍历nums2
        for (int i : nums2){
            if (set1.contains(i)){
                ansSet.add(i);
            }
        }
        int answer[] = new int[ansSet.size()];
        int x = 0;
        for (int i : ansSet){
            answer[x] = i;
            x++;
        }
        return answer;
    }
}

202. 快乐数

注意点：取n的各位的平方和的写法

class Solution {
    public boolean isHappy(int n) {
        // 哈希set存储已出现的数
        Set<Integer> sums = new HashSet<>();
        sums.add(n);
        // 数不为1则继续循环取各位的平方和
        while (n != 1){
            n = sumofPower(n);      // 下一个数
            if (sums.contains(n)){  // 循环出现
                return false;
            }else{
                sums.add(n);        // 加入哈希set
            }
        }
        return true;                // 变为1，返回true
    }
    // 取n的各位的平方和
    public int sumofPower(int n){
        int ans = 0;
        while (n > 0){          // 终止条件
            int tmp = n % 10;   // 取个位
            ans += tmp * tmp;   // 平方和
            n = n / 10;         // n去掉个位
        }
        return ans;
    }
}

1. 两数之和

方法1.暴力法两层for循环

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        for (int i = 0; i < nums.length -1; i++ ){//两层for循环暴力求解
            for (int j = i +1 ; j < nums.length; j++){
                if (nums[i] + nums[j] == target){
                    ans[0] = i;
                    ans[1] = j;
                    break;
                }
            }
        }
        return ans;
    }
}

方法2.创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

注意点：HashMap的写法：Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>()

HashMap是Java中最常用的映射类型的数据结构。主要特点是：

1. 存储键值对(key-value)映射。key和value可以是任何引用类型。

2. 根据键快速查询值。底层采用哈希表,查询效率很高。

3. 键不重复,值可以重复。

4. 线程不安全,效率高。

常见的HashMap方法有：

1. put(key, value): 添加键值对。如果key已存在,更新值。

2. get(key): 根据键查询值。

3. remove(key): 根据键移除键值对。

4. size(): 返回映射个数。

5. isEmpty(): 判断是否为空。

6. containsKey(key): 判断是否包含键。

7. containsValue(value): 判断是否包含值。

class Solution {
    public int[] twoSum(int[] nums, int target) {// 哈希map
        Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++){                      // 遍历数组
            if (hashMap.containsKey(target - nums[i])){             // 是否包含键
                return new int[]{i, hashMap.get(target - nums[i])}; 
            }
            hashMap.put(nums[i], i);                                // 加入map
        }
        return new int[0];
    }
}