Day05

今日任务?

• ?哈希表理论基础?
• ?242.有效的字母异位词?
• ?349.?两个数组的交集?
• ?202.?快乐数
• ?1.?两数之和

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

---

242 有效的字母异位词

题目链接：https://leetcode.cn/problems/valid-anagram/description/

关键：因为都是小写字母，所有每一位字符都可以与? 字符 a 进行做差，便可以得到 0-25 的数值

思路：

1. 先判断两个字符串长度是否一致，不一致直接排除
2. 遍历两个字符串，一个负责加数组，一个负责减数组
3. 最终得到的数组如果全为 0，则为 true；否则 false??

代码：

lass Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) {
            return false;
        }
        int[] abc = new int[26];
        for(int i = 0; i < s.length(); i++) {
            abc[s.charAt(i) - 'a']++;
            abc[t.charAt(i) - 'a']--;
        }
        for(int i = 0; i < 26; i++) {
            if(abc[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

---

349?两个数组的交集

题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/description/

关键： set 存放数据时不重复的

思路：

1. 创建两个新集合 HashSet，元素不可重复，分别遍历两个数组，并放入集合
2. 遍历短的集合元素，判断是否被长集合包含
3. 将长集合包含的元素，放进一个新集合
4. 将集合转为数组输出

代码：有一个很优雅的数据互换

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for(int num : nums1) {
            set1.add(num);
        }
        for(int num : nums2) {
            set2.add(num);
        }
        //这时就需要遍历 不大的集合数据，去判断是否在大的集合里出现过
        return getIntersection(set1, set2);
    }
    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
        //优雅实现互换
        if(set1.size() > set2.size()) {
            return getIntersection(set2, set1);
        }
        //这里就已经确保 set1 是 数据少的集合
        Set<Integer> res = new HashSet<Integer>();
        for(int num : set1) {
            if(set2.contains(num)) {
                res.add(num);
            }
        }
        int[] ans = new int[res.size()];
        int index = 0;
        for(int num : res) {
            ans[index++] = num;
        }
        return ans;
    }
}

---

202?快乐数

题目链接：https://leetcode.cn/problems/happy-number/description/

关键： 要理解都有哪些情况！！！

猜测只有三种：

1. 最终会得到?1
2. 最终会进入循环
3. 值会越来越大，最后接近无穷大

?可以看出它是会在特别大的时候变小，不会无限期地进行下去，所以我们排除第三种选择

代码：

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> nums = new HashSet<>();
        while( n != 1 && !nums.contains(n)) {
            nums.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    public int getNext(int n) {
        int total = 0;
        while(n > 0) {
            int d = n % 10;
            n = n / 10;
            total += d * d;
        }
        return total;
    }
}

---

1?两数之和

题目链接：https://leetcode.cn/problems/two-sum/description/

暴力解法：不推荐

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = {0, 0};
        for(int i = 0; i<nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if((nums[i] + nums[j]) == target) {
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        return res;
    }
}

关键： 利用哈希表 去查找 target - x ，可以大大降低时间复杂度

代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i],i);
        }
        return new int[0];
    }
}