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

先学习一下前置知识：哈希表理论基础

使用场景：快速判断一个元素是否出现集合里，牺牲了空间换取了时间。

定义：哈希表是根据关键码的值而直接进行访问的数据结构。

疑问点：保证映射出来的索引数值都落在哈希表上，再次对数值做一个取模的操作。

哈希碰撞：如果数据量大于哈希表的大小，此时就算哈希函数计算的再均匀，也避免不了会有不同的数据同时映射到哈希表同一个索引下标的位置。用拉链法（发生冲突的元素都被存储在链表中）、线性探测法（一定要保证表大小大于数据量，依靠哈希表中的空位来解决碰撞问题，向下找一个空位放置重复信息）。

242.有效的字母异位词

文字讲解：有效的字母异位词

视频讲解：学透哈希表，数组使用有技巧！

题设：给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

难点：选用数据结构。

思路：数组、set （集合）、map（映射），三选一。范围可控，数据较小（26个字母），采用数组。遍历原字符串在元素位置加上出现次数，新字符串在元素位置减去出现次数，最后判断数组是否为0数组。

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 i = 0; i < hash.length; i++) {
        if (hash[i] != 0) {
            return false;
        }
    }
    return true;
}

易错点：对于数组的加减处理的思路不好想。

复杂度分析：

时间复杂度为O(n)。
空间上因为定义了一个常量大小的辅助数组，所以空间复杂度为O(1)。

349. 两个数组的交集

文字讲解：两个数组的交集

视频讲解：学透哈希表，set使用有技巧！

题设：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。

难点：数据结构选择。

思路：数值分布分散，数值可能很大，采用set。Java可以直接创建哈希表，其中元素不允许重复，因此也不需要考虑去重操作。

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> result = new HashSet<>();
    Set<Integer> numSet = new HashSet<>();
    for (int i : nums1) {
        numSet.add(i);
    }
    for (int i : nums2) {
        if (numSet.contains(i)) {
            result.add(i);
        }
    }
    int[] res = new int[result.size()];
    int j = 0;
    for (Integer i : result) {
        res[j++] = i;
    }
    return res;
}

易错点：set相关的使用方法，尤其是遍历方法的形式。最后返回为数组形式，因此还需要一次转换。

复杂度分析：

时间复杂度: O(m + n)。
空间复杂度: O(n)。

202. 快乐数

文字讲解：快乐数

题设：编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为1，也可能是 无限循环 但始终变不到 1。
如果这个过程结果为1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

难点：题意理解。

思路：关键在于，如果sum值产生了循环，意味着永远无法变成1。判断sum值是否出现在此前的结果中，采用哈希法。由于数据大小不固定较分散，所以用set解决。

public boolean isHappy(int n) {
    Set<Integer> record = new HashSet<>();
    while (n != 1 && !record.contains(n)) {
        record.add(n);
        n = getNew(n);
    }
    return n == 1;
}
private int getNew(int n) {
    int newNum = 0;
    while (n > 0) {
        int i = n % 10;
        n /= 10;
        newNum += i * i;
    }
    return newNum;
}

易错点：循环终止条件的细节，以及最后判断是精髓所在，两种结果情况即为循环终止的两种条件。

复杂度分析：

时间复杂度: O(log n)。
空间复杂度: O(log n)。

1. 两数之和

文字讲解：两数之和

视频讲解：梦开始的地方，map使用有技巧！

题设：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

难点：初见思路，力扣第一题实际难度不小。

思路：需要寻找目标值减去当前值后的结果是否在此前遍历过程中出现过。由于查找后要返回下标，因此光是set和数组都不够用了，因此采用map的方式。将元素值设置为key，因为目的是要找是否出现过此值，下标才是value（要返回的值）。

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        if (map.containsKey(temp)) {
            res[0] = i;
            res[1] = map.get(temp);
            break;
        }
        map.put(nums[i], i);
    }
    return res;
}

易错点：对于map的作用，存放的数据含义，value和key的混淆。

复杂度分析：

时间复杂度: O(n)。
空间复杂度: O(n)。