🍎道阻且长，行则将至。🍓

🌻算法，不如说它是一种思考方式🍀

算法专栏： 👉🏻123

@[TOC]

一、🌱242. 有效的字母异位词

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

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

• 来源：力扣（LeetCode）
• 难度：简单
• 提示：

1 <= s.length,t.length <= 5*10^4^
s 和 t 仅包含小写字母

• 示例 1:

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

🌾分析：

对于这里在多个内容中找是否出现有某内容，可以使用hash表-哈希表。

1.什么是哈希表？

哈希表是根据关键码的值而直接进行访问的数据结构。就可以认为是一个数组，关键码就是指这个元素一个存储在数组的哪个位置。在👉🏻Set集合里面就有个HashSet，会根据hashcode（哈希值）来存储元素。
要在一个数组中查找一个元素，去一个个遍历，这个复杂度就是O(n)，而使用哈希表复杂度是O(1)。
在哈希表存储元素的过程中，可能存储的元素得到的哈希值大于你的数组下标，我们通常会对哈希值进行取余操作后放入对应的数组位置。
然而这个时候又有可能几个元素取余之后的元素是一样的，那不可能把几个元素放到一个数组格子里吧！这就是哈希碰撞。解决这类问题的方法有两种：拉链法和线性探测法。

1. 拉链法

拉链那个当然是拉出一个链表结构来解决冲突了，就是说把发送冲突的元素存储在链表中，以后查找到哈希值直接到链表里寻找。这一类方法要选择好合适的哈希表长度，避免浪费哈希表的数组空间，也同时避免过长的链表减低查找性能。

1. 线性探测法

线性探测就是探测到发生冲突就存储到哈希表的下一位，这种方法也就要求哈希表长度大于数据长度。

2.哈希表的数据结构

前面提到哈希表可以使用数组、set集合，其实哈希表还可以使用map，java基础篇👉🏻提到的hashset和hashmap，参考：Map集合的使用-Java。map是一种key-value的存储结构，可以用key保存数值，用value在保存数值所在的下标。

🌴解题

• 数组

题目说明了都是小写字母字符，所以直接使用数组长度为26，记录每个字母在s中出现的次数，抵消t中出现的次数，最后遍历数组，不为0就是出现次数不相同。

• code：

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

二、🌱349. 两个数组的交集

• 题目描述：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以==不考虑输出结果的顺序==。
• 来源：力扣（LeetCode）
• 难度：简单
• 提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

• 示例 1:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

🌴解题

• HashSet

题目要求我们找到两个数组元素的相同元素，当然也可以使用for循环暴力解决（ 是==O(n^2^) 的==时间复杂度），但是我们使用哈希表可以更简单（哈希查找是==O(1) 的==时间复杂度，整体复杂度是==O(n) 的==）。我们可以建立两个哈希集合，先把第一个数组加进集合，遍历第二个数组的时候如果对于元素出现在集合中就把改元素存储下来，最后得到结果。

• code：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {

        Set<Integer> a1=new HashSet<>();
        Set<Integer> a2=new HashSet<>();
        for (int i = 0; i < nums1.length; i++) {
            a1.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            if(a1.contains(nums2[i]))
                a2.add(nums2[i]);
        }
        int[] ans=new int[a2.size()];
        int i=0;
        for (int o : a2) {
            ans[i++]=o;
        }

        return ans;
    }
}

返回第一页。☝

☕物有本末，事有终始，知所先后。🍭