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

242.有效的字母异位词

---

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

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: s和t字符串只包含小写字母。（这句话可以想到用数组当做哈希表）

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

思路：
数组本身就可以当成是哈希表，因为题中统计的是小写字符，a-z是26个，定义一个26大小的数组记录a-z出现的次数，a，b...对应数组下表是0,1...
遍历第一个字符串，利用Hash【s[i] - 'a'】++ 来表示字符a，b对应的下标为0,1，统计字符出现的次数；
遍历第二个字符串，利用Hash【s[i] - 'a'】--
最后遍历Hash，如果出现都是0，说明是有效字母异位词

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

349. 两个数组的交集

---

HashSet是无序，不重复，无索引

题意：给定两个数组，编写一个函数来计算它们的交集。

但是要注意， 使用数组来做哈希的题目，是因为题目都限制了数值的大小。
而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。
不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。

但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。

不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。

注意：set2.stream().mapToInt(Integer::intValue).toArray() 是将Set<Integer>转化为Int类型的数组
.toArray() 是将集合转化为数组的方法

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        //if(nums1 == null || nums1.length == 0 ||nums2.length == 0 || nums2 == null){
          //  return new int[0];
        //}
         for(int i : nums1){
             set1.add(i);
         }
         for(int j : nums2){
             if(set1.contains(j)){
                set2.add(j);
             }
         }
        //方法1：将结果集合转为数组
         return set2.stream().mapToInt(x->x).toArray();
        
        //方法2：另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[setRes.size()];
        int j = 0;
        for(int i : setRes){
            arr[j++] = i;
        }
        
        return arr;
    }
}

202题. 快乐数

---

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

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

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19输出：true解释：1^2 + 9^2 = 828^2 + 2^2 = 686^2 + 8^2 = 1001^2 + 0^2 + 0^2 = 1

这道题目看上去貌似一道数学问题，其实并不是！

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

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

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

补充知识：“不是快乐数的数称为不快乐数（unhappy number），所有不快乐数的数位平方和计算，最后都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set1 = new HashSet<>();
        //要先判断一次n，因为n很有可能是1
        while(n != 1 && !set1.contains(n)){//这表示n如果不是1，并且集合中不包含这个数才添加，集合中出现这个数说明进入循环了
            set1.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
 
 
    }
    public int getNextNumber(int n){
        int res = 0;
        while(n > 0){
            int temp = n % 10;//获取个位
            res += temp * temp;
            n = n / 10;//移动到是十位，并且做条件判断
        }
        return res;
    }
}

思路：
注意这个getNextNumber这个方法，很巧妙，利用循环得到一个数的各个数位，进行处理
重点看isHappy()方法的逻辑，!set1.contains(n)表示不包含n返回值是true
利用循环，将每一次计算的值存入集合中，之后再进行计算

我们知道Set集合是可以去重的，就是没有相同的元素。在执行add方法时候，如果这个元素已经在set中存在，那么就返回false，否则返回true

1. 两数之和

---

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

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

暴力枚举

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){//不包含重复元素
                int sum = 0;
                sum = nums[i] + nums[j];
                if(sum == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }
}

哈希算法

首先我在强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

本题呢，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是是否出现在这个集合。

map中的存储结构为 {key：数据元素，value：数组元素对应的下表

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map1 = new HashMap<>();
        //if(nums == null || nums.length == 0){
          //  return nums;
        //}
        //题中声明了2 <= nums.length <= 104
        int[] res = new int[2];
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map1.containsKey(temp)){
                res[0] = i;
                res[1] = map1.get(temp);
                break;
            }
                map1.put(nums[i],i);
        }
        return res;
    }
}

思路： 相当于拿遍历到的数组的值与map集合中的元素做和