哈希表

哈希表的基础知识在我的另一份文件，左程云算法学习中有过介绍，这里不再记录

242.有效的字母异位词

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

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

思路：第一反应就是构造一个数组，长度为26，a-0,z-25,统计词频，两个字符串对应两个数组，最后比较两个数组即可，时间复杂度应该是O(3*N)
代码随想录的方法是用一个数组，第一个++，第二个--，最后看是否数组都为0判断，更能省下来空间
进阶题目要求，如果字符串包含unicode字符怎么办
- 第一反应思路是用一个很长的数组，不好，内存开销太大；接着想到用一个HashMap来实现，key放字符，value统计词频

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

349.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序

思路：像242一样，两个数组统计词频，arr1[i] != 0 && arr2[i] != 0就是我们要找的i，写的过程中发现这样有一个问题，只是输出还好，返回数组的话不好搞。得拿个list先统计有哪些词，再把List存到数组。
然后看随想录的分析，用set集合，遍历第一个数组统计有哪些数，一边统计一边加入set集合，再遍历第二个数组，同时看前一个set是否有第二个数组的元素，有就加入第二个set集合，最后把第二个Set转到int[]。（C++就不用转了，更方便）
由于数组中元素大小有限，可以用数组做哈希表，最开始我没考虑到数字可能太大不能用数组的情况

//我的实现
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] arr1 = new int[1005];
        int[] arr2 = new int[1005];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
             arr1[nums1[i]]++;
        } 
        for (int i = 0; i < nums2.length; i++) {
             arr2[nums2[i]]++;
        }
        for (int i = 0; i < 1005; i++) {
            if (arr1[i] != 0 && arr2[i] != 0) {
                list.add(i);
            }
        }
        for(Integer a : list) {
            System.out.print(a);
        }
        int[] arr = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;
    }
}

350.两个数组的交集

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

思路：两个哈希表，分别统计词频，最后遍历第一个哈希表的key，第二个哈希表若包含这个key，就map.get()比较大小，较小的那个值赋值给第三个哈希表，最后第三个哈希表转化为数组
看了官方题解后发现官方的优化在于，节约两个哈希表，只用哈希表统计第一个数组的词频，==注意选择数组长度较小的那个当第一个数组==，遍历第二个数组，如果哈希表包含这个元素，就将第一个表的对应value--，同时将这个元素加入到结果数组。
官方还有一个方法，排序+双指针法，两个数组先排序，然后指针指向头部，不断比较指针指向元素的大小。
进阶三问可以看leetcode的题解

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map1 = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map1.put(nums1[i], (map1.getOrDefault(nums1[i],0)) + 1);
        }
        for (int i = 0; i < nums2.length; i++) {
            map2.put(nums2[i], (map2.getOrDefault(nums2[i],0)) + 1);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int total = 0;
        for (int key : map1.keySet()) {
            if (map2.containsKey(key)) {
                int small = Math.min(map1.get(key),map2.get(key));
                map.put(key, small);
                total += small;
            }
        }
        int[] arr = new int[total];
        int i = 0;
        for (int key : map.keySet()) {
            int temp = map.get(key); 
            while(temp-- != 0){
                arr[i++] = key;
            }
        }
        return arr;

    }
}

1.两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

思路：两个for循环暴力递归实现
进阶题目要求时间复杂度小于O(n^2)：
- 自己看到的时候想的是能不能有一种方法，可以让我在指针指到数组后面的数的时候，能够回头判断前面的数是否出现过，想到了双指针，但是仔细思考后发现双指针好像没什么卵用，时间复杂度还是O(N^2)
- 看了答案，发现是用哈希表来解决的，在代码随想录中有如下总结：
- 首先我再强调一下 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

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++) {
                if( (nums[i] + nums[j]) == target)
                return new int[]{i, j};
            }
        }
        return new int[]{0};
    }
}

进阶版——使用哈希表

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

        }
        return new int[]{};
    }