[数据结构与算法]LeetCode：哈希表篇

一、理论基础

1.1 哈希表（散列表）

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

• 其实数组就是一张哈希表。

• 关键码就是数组的索引下标，可以通过下标直接访问数组中的元素

解决什么问题：快速判断一个元素是否出现在集合里

1. 通过元素的 hashCode() 参与计算得到 hash值
2. 让 hash值 参与哈希函数的计算得到数组的索引下标，然后进行判断

1.2 哈希函数

• 哈希函数：将hash值(元素)散列在数组上

1.3 哈希碰撞

1. 元素个数大于数组大小
2. 两个元素计算出来的索引下标相同

1.3.1 拉链法

• 元素个数大于数组大小
• 数组大小设置要适当：既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

1.3.2 线性探测法

• 保证元素个数小于数组大小
• 哈希碰撞则使用数组下一个空位存放

1.3 常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

1.4 总结

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

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法！

二、LeetCode题序

• 数组
• Set
• Map
• 双指针法：27、15、18

242 (简单)有效的字母异位词

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

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

• 仅包含小写字母

/**
 * 思路：数组，与383类似
 *	将字符串中的字符映射为大小26的int数组的下标
 * 	 1.遍历s串：将元素对应数组索引的值+1
 * 	 2.遍历t串：将元素对应数组索引的值-1
 * 	 3.最后判断数组中的元素值是否都为0
 */
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] count=new int[26];
        //1.遍历s串：将数组对应的元素值+1
        for(int i=0;i<s.length();i++){
            count[s.charAt(i)-'a']++;
        }
        //2.遍历t串：将数组对应的元素值-1
        for(int i=0;i<t.length();i++){
            count[t.charAt(i)-'a']--;
        }
        //3.最后判断数组中的元素值是否都为0
        for(int i=0;i<count.length;i++){
            if(count[i]!=0) return false;
        }
        return true;
    }
}

1002 (简单)查找常用字符

给你一个字符串数组 words ，请你找出所有在 words 的每个字符串中都出现的共用字符（ 包括重复字符），并以数组形式返回。你可以按 任意顺序 返回答案。

• 输入：words = [“bella”,“label”,“roller”] 输出：[“e”,“l”,“l”]
• 由小写英文字母组成

/**
 * 思路：两个频数数组
 *	1.取出数组中的前两个字符串找出重复字符
 *	2.循环下一个字符串：与之前的重复字符进行比较，再次取出重复字符
 */
class Solution {
    public List<String> commonChars(String[] words) {
        //1.存储遍历数组时前面字符串存在的重复字符和重复次数
        int[] count=new int[26];
        //2.存储遍历数组时当前字符串字符出现次数
        int[] buf=new int[26];
        //3.存储结果
        List<String> list=new ArrayList();
        //4.是否为第一次计算重复字符
        boolean isOne=true;
        for(String str:words){
            //初始化count
            if(isOne) {
                for(int i=0;i<str.length();i++){
                    count[str.charAt(i)-'a']++;
                }
                isOne=false;
                continue;
            }
            //获取当前字符串字符频数数组
            for(int i=0;i<str.length();i++){
                buf[str.charAt(i)-'a']++;
            }
            //将当前字符串与上一字符串的字符频数数组进行合并，取更小值
            for(int i=0;i<26;i++){
                count[i]=Math.min(count[i],buf[i]);
                buf[i]=0; //注意清0
            }
        }
        for(int i=0;i<26;i++){
            for(int j=0;j<count[i];j++){
                list.add(String.valueOf((char)(i+'a')));
            }
        }
        return list;
    }
}

349 (简单)两个数组的交集

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

/**
 * 思路：Set
 *	1.将第一个数组转换为Set
 *	2.遍历第二个数组，如果set集合中存在则为交集
 */
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set=new HashSet();
        Set<Integer> result=new HashSet();
        //1.将第一个数组转换为Set
        for(int data:nums1){
            set.add(data);
        }
        //2.遍历第二个数组，如果set集合中存在则为交集
        for(int data:nums2){
            if(set.contains(data)) result.add(data);
        }
        return result.stream().mapToInt(x->x).toArray();
    }
}

202 (简单)快乐数

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

「快乐数」 定义为：

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

/**
 * 思路：Set
 *	1.循环计算平方和，将每次计算的结果存放在Set中
 *	2.平方和为1，返回true。
 *	3.平方和不为1：判断是否存在Set，存在则是无限循环返回false。不存在则添加到Set
 */
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> sums=new HashSet();
        while(n!=1 && n>=0){
            //1.循环计算平方和，将每次计算的结果存放在Set中
            sums.add(n);
            n=sum(n);
            //3.平方和不为1：判断是否存在Set，存在则是无限循环返回false。不存在则添加到Set
            if(sums.contains(n)) return false;
        }
        //2.平方和为1，返回true。
        return n==1?true:false;
    }
    public int sum(int n){
        int sum=0;
        while(true){
            sum=sum+(n%10)*(n%10);
            n=n/10;
            if(n==0) break;
        }
        return sum;
    }
}

1 (简单)两数之和

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

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

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

• 双指针法超出时间限制

/**
 * 思路：Map
 *	遍历数组元素
 *	 1.通过target-nums[i]计算需要的另一个元素值，在map中查找
 *	 2.map中不存在：将当前元素的值作为key，索引作为value放入map中
 *	 3.map中存在：返回 i、另一个元素值在map中的value
 */
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result=new int[2];
        if(nums==null || nums.length==0) return result;
        Map<Integer,Integer> map=new HashMap();
        //遍历数组元素
        for(int i=0;i<nums.length;i++){
            //1.通过target-nums[i]计算需要的另一个元素值，在map中查找
            int need=target-nums[i];
            //3.map中存在：返回 i、另一个元素值在map中的value
            if(map.containsKey(need)){
                result[0]=map.get(need);
                result[1]=i;
            }
            //2.map中不存在：将当前元素的值作为key，索引作为value放入map中
            map.put(nums[i],i);
        }
        return result;
    }
}

454 (中等)四数相加II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

/**
 * 思路：Map
 *	1.先遍历nums1、nums2 计算元素之和：统计和出现的次数存放在map中
 *	2.遍历nums3、nums4 计算与元素和相加等于0的值：统计与map中元素相加等于0的次数
 */
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map=new HashMap();
        int sum=0;
        //1.先遍历nums1、nums2 
        for(int v1:nums1){
            for(int v2:nums2){
                //计算元素之和
                sum=v1+v2;
                Integer value=null;
                if((value=map.get(sum))!=null) {
                    //统计和出现的次数存放在map中
                    map.put(sum,value+1);
                }else{
                    map.put(sum,1);
                }
            }
        }
        int result=0;
        //2.遍历nums3、nums4
        for(int v3:nums3){
            for(int v4:nums4){
                sum=v3+v4;
                //计算与元素和相加等于0的值
                int need=0-sum;
                Integer value=null;
                if((value=map.get(need))!=null) {
                    //累加该值作为key在map中的value
                    result+=value;
                }
            }
        }
        return result;
    }
}

383 (简单)赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

• 如果可以，返回 true ；否则返回 false 。

• magazine 中的每个字符只能在 ransomNote 中使用一次。

• 两个字符串由小写英文字母组成

/**
 * 思路：数组，与242类似
 *	将字符串中的字符映射为大小26的int数组count的下标
 * 	 1.遍历ransomNote串：将元素对应count数组索引的值+1
 * 	 2.遍历magazine串：将元素对应count数组索引的值-1
 * 	 3.最后判断count数组中的元素值是否存在大于1的情况
 */
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count=new int[26];
        for(int i=0;i<ransomNote.length();i++){
            count[ransomNote.charAt(i)-'a']++;
        }
        for(int i=0;i<magazine.length();i++){
            count[magazine.charAt(i)-'a']--;
        }
        for(int i=0;i<26;i++){
            if(count[i]>0) return false;
        }
        return true;
    }
}

15 (中等)三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

/**
 * 三指针法
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new ArrayList();
        Arrays.sort(nums);	//排序：为了去重
        //1.固定i
        for(int i=0;i<nums.length-2;i++){
            if (nums[i] > 0) return result;	//剪枝
            if (i > 0 && nums[i] == nums[i - 1]) {  //去重
                continue;
            }
            
            //2.定义左指针
            int left=i+1;
            //3.定义右指针
            int right=nums.length-1;
            //4.循环定位左、右指针
            while(left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0) {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left<right && nums[left]==nums[left+1]) left++;	//去重
                    while(left<right && nums[right]==nums[right-1]) right--;	//去重
                    left++;
                    right--;
                }else if(sum<0){
                    left++;	//无需考虑去重，因为不满足条件不会加入结果集中
                }else if(sum>0){
                    right--; //无需考虑去重，因为不满足条件不会加入结果集中
                }
            }
        }
        return result;
    }
}

18 (中等)四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：【1，2，3，4】与【4，3，2，1】重复

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target
• 你可以按 任意顺序 返回答案 。

/**
 *	四指针法：与三数之和类似
 */
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result=new ArrayList();
        Arrays.sort(nums);
        //1.固定i
        for(int i=0;i<nums.length-3;i++){
            if(nums[i] >0 && nums[i]-target>0) return result;	//剪枝操作
            if(i>0 && nums[i-1] == nums[i]) continue;	//去重
            //2.固定j
            for(int j=i+1;j<nums.length-2;j++){
                if(j>i+1 && nums[j-1]==nums[j]) continue;	//去重
                //3.移动左、右指针
                int left=j+1;
                int right=nums.length-1;
                while(left<right){
                    int sum=nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum==target) {
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left<right && nums[left]==nums[left+1]) left++;	//去重
                        while(left<right && nums[right]==nums[right-1]) right--;	//去重
                        left++;
                        right--;
                    }else if(sum<target){
                        left++;	//无需考虑去重，因为不满足条件不会加入结果集中
                    }else if(sum>target){
                        right--; //无需考虑去重，因为不满足条件不会加入结果集中
                    }
                }
            }
        }
        return result;
    }
}