算法系列--哈希表

💕"白昼之光，岂知夜色之深。"💕
作者：Mylvzi
文章主要内容：算法系列–哈希表

今天为大家带来的是算法系列--哈希表

1.两数之和

链接:
https://leetcode.cn/problems/two-sum/submissions/515941642/

分析:

有人相爱，有人夜里开车看海，有人leetcode第一题都做不出来。

最容易想到的思路就是暴力解法,每遍历到一个数字,就去从头遍历看有没有相加符合条件的数字,但是这样的时间复杂度达到了O(N^2),使用哈希表可以降低到O(N)

之所以是n^2是因为我么在查找第二个数的时候又套了一层for循环,既然涉及到在一堆数中快速查找某一个数,就可以使用hash表进行优化,思路如下:

每遍历到一个数,就将其数值和下标存入到哈希表之中
判断哈希表中是否存在target-nums[i]的数字,如果有返回这两个数的下标,如果没有继续遍历

代码:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 使用哈希表建立数字与下标之间的映射关系
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 去看是否包含target-i
            if(map.containsKey(target-nums[i])) {
                return new int[]{map.get((target-nums[i])),i};// 返回下标
            }
            
            map.put(nums[i],i);
        }
        
        return null;
    }
}

2.判断是否互为字符重排

链接:
https://leetcode.cn/problems/check-permutation-lcci/description/

分析:
本题最直观的想法就是创建出两个哈希表,分别存储字符串中的所有内容,最后判断两个哈希表是否相同即可

代码:

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) return false;
        Map<Character,Integer> hash1 = new HashMap<>();
        Map<Character,Integer> hash2 = new HashMap<>();
        for(char c1 : s1.toCharArray()) {
            hash1.put(c1,hash1.getOrDefault(c1,0) + 1);
        }

        for(char c2 : s2.toCharArray()) {
            hash2.put(c2,hash2.getOrDefault(c2,0) + 1);
        }

        return hash1.equals(hash2);
    }
}

注意本题还可以使用排序的思想,将两个字符串进行排序,然后直接判断是否相同即可

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) return false;

        char[] ss1 = s1.toCharArray();
        char[] ss2 = s2.toCharArray();

        Arrays.sort(ss1);
        Arrays.sort(ss2);

        return Arrays.equals(ss1, ss2);
    }
}

只有使用Arrays.equals()这个方法才能判断数组中的内容是否相同,因为里面重写了equals方法,如果直接比较,比较的是地址

3.存在重复元素 I

链接:
https://leetcode.cn/problems/contains-duplicate/description/

分析:

使用set来判断是否出现重复元素

代码:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int n : nums) {// add()的返回值是布尔类型
            if(!set.add(n)) return true;
        }

        return false;
    }
}

注意: add()的返回值是布尔类型,用于表示此次添加是否成功.set具有去重的功能,如果添加的元素已经存在,就会添加失败

4.存在重复元素 II

链接:
https://leetcode.cn/problems/two-sum/submissions/515941642/https://leetcode.cn/problems/contains-duplicate-ii/description/

分析:

结合题意解决即可

代码:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(hash.containsKey(nums[i]) && Math.abs(hash.get(nums[i]) - i) <= k) 
                return true;
            hash.put(nums[i],i);
        }
        
        return false;
    }
}

5.字⺟异位词分组

链接:
https://leetcode.cn/problems/group-anagrams/description/

分析:

本题更像是一道语法题,充分利用了java 的Map容器,相同的字母异位词指的是两个字符串中所包含的字符完全相等,也就是将他们按照ascii码值排序之后得到的结果完全相同,我们设这个排序之后的结果为pivot,那么我们就可以利用哈希表建立<pivot,List<String>>之间的映射关系

对字符串进行排序,得到其pivot
如果哈希表中不存在pivot,就新创建一个;如果存在,得到pivot对应的list,让其添加当前的字符串

代码:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> hash = new HashMap<>();

        // 先对所有的字符串进行异或分组
        for(String str : strs) {
            char[] tmp = str.toCharArray();
            Arrays.sort(tmp);// 排序  得到pivot
            String key = new String(tmp);// 转化为字符串
            
            List<String> list = hash.getOrDefault(key, new ArrayList<String>());// 注意有可能不存在
            list.add(str);// 添加上当前的字符串
            hash.put(key,list);// 插入哈希表
        }
        
        return new ArrayList(hash.values());// 注意这个语法!可以直接返回hash的所有value的集合
    }
}