算法通关 - 哈希表

哈希表（HashMap&HashSet）

哈希表是一种建立映射关系的数据结构，保存key和value。它的主要实现是数组+链表的数据结构，首先对key进行哈希算法操作，得到value在哈希表中要存储的数组下标，然后将value值存储。

这种实现就会有一个问题，如果两个key通过哈希算法得到的下标是相同的，那么就会产生哈希冲突。所以当产生哈希冲突时，就需要通过链表来保存下标计算相同的value值，每个value的next指针指向下一个value

哈希表的优势是查找速度快，只需要O(1)的时间复杂度。如果通过数组查找，时间复杂度是O(n)，所以在需要快速查找的时候可以考虑哈希表这种数据结构。Java中两种常用的哈希表实现就是HashMap和HashSet

List vs Map vs Set

List 、Map 和 Set都是抽象型的数据结构，是一种统称，具体的实现可以有很多种。

• List的实现可以是数组也可以是链表，List的特点是元素可以重复，并放在一个表里面。List的插入操作时间复杂度是O(1)，查找的时间复杂度是O(n)
• Map就是建立的key和value的映射关系。
• Set（集合）和Map比较相似，Set中不允许有重复的元素，它里面的元素可以看做是Map中的key，而且HashSet底层也是通过HashMap来实现的。Set的实现方法有两种，一般来说是通过哈希表或者二叉树的形式来实现。所以查找的时间复杂度是O(1)或者O(longn)，比List的查找效率更高。

HashMap vs TreeMap、HashSet vs TreeSet

map的常用的两种实现形式是HashMap 和 TreeMap，set常用的两种实现形式则是HashSet 和 TreeSet。从功能上来说，两种方式所达到的效果是一样的，只是实现形式不同。分别通过哈希表和二叉树的方式实现。

从查找效率上来说，通过哈希表实现的HashMap 和 HashSet，查找时间复杂度是O(1)，而通过二叉树实现的TreeMap 和 TreeSet的查找时间复杂度是O(logn)。二叉树的查找虽然比不上哈希表，但它的优势是二叉树中元素是排好序的，是相对有序的一种排列，哈希表则是乱序的。在实际使用过程中还要根据具体情况来选择时使用哈希表还是二叉树的结构。

1.有效的字母异位词（LeetCode - 242）

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。说明:你可以假设字符串只包含小写字母。

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

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

方法一：排序，直接通过对两个字符串进行排序，并比较排序后的字符串是否相等。如果相等则是异位词

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

• 时间复杂度：O(nlogn)，假设 n 是 s 的长度，排序成本 O(nlogn) 和比较两个字符串的成本 O(n)。排序时间占主导地位，总体时间复杂度为O(nlogn)。

• 空间复杂度：O(1)，空间取决于排序实现，如果使用 heapsort，通常需要O(1) 辅助空间。注意，在 Java 中，toCharArray() 制作了一个字符串的拷贝，所以它花费 O(n) 额外的空间，但是我们忽略了这一复杂性分析，因为：这依赖于语言的细节，取决于函数的设计方式。例如，可以将函数参数类型更改为 char[]。

  ​

方法二：哈希表，通过两个HashMap分别记录两个字符串中每个字符出现的次数，map中key是字符，value是出现的次数，最后比较两个map是否相等来判断。

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        HashMap<String,Integer> sMap = new HashMap<String,Integer>();
        HashMap<String,Integer> tMap = new HashMap<String,Integer>();
        for(int i = 0;i < s.length();i++){
            String sletter = String.valueOf(s.charAt(i));
            String tletter = String.valueOf(t.charAt(i));
            if(sMap.containsKey(sletter)){
                int count = sMap.get(sletter).intValue();
                sMap.put(sletter,Integer.valueOf(++count));
            }else{
                sMap.put(sletter,1);
            }

            if(tMap.containsKey(tletter)){
                int count = tMap.get(tletter).intValue();
                tMap.put(tletter,Integer.valueOf(++count));
            }else{
                tMap.put(tletter,1);
            }
        }

        return sMap.equals(tMap);
    }
}

• 时间复杂度：O(n)。时间复杂度为 O(n) 因为访问计数器表是一个固定的时间操作。

• 空间复杂度：O(1)。尽管我们使用了额外的空间，但是空间的复杂性是O(1)，因为无论 N 有多大，表的大小都保持不变。

通过哈希表的方式来判断适用于字符串包含 unicode 字符的情况，如果可以确定字符串中只有字母的话，使用如下两种简单方法可以更快速地判断。

//因为 s 和 t 都只包含 A−Z 的字母，所以一个简单的 26 位计数器表就足够了。而且我们并需要两个计数器数表进行比较，可以用一个计数器表增加 s 中字母出现的频率，用 t 减少计数器表中的每个字母的计数器，然后检查计数器是否回到零。

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

//我们可以先用计数器表计算 ss，然后用 tt 减少计数器表中的每个字母的计数器。如果在任何时候计数器低于零，我们知道 tt 包含一个不在 ss 中的额外字母，并立即返回 false

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

​

两数之和（LeetCode - 1）

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。实例：

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法一：暴力法。通过两层嵌套循环找到对应的下标并返回

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[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

• 时间复杂度：O(n²)，对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n²)

• 空间复杂度：O(1)

方法二：哈希表。循环遍历将元素插入到表中的同时，同时回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们就已经找到了对应解，并立即将其返回。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

• 时间复杂度：O(n)，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。

• 空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。

三数之和（LeetCode - 15）

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

方法一：暴力法。通过三层嵌套循环来查找三数之和等于零的元素。这种时间复杂度是O(n³)

方法二：哈希表。首先将整个数组存放到一个set集合中，然后只需要枚举a和b，最后判断 -(a+b) 是否在set集合中即可。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums ==null || nums.length == 0){
            return new ArrayList();
        }
        List<List<Integer>> resultList = new ArrayList();
        //要先对数组进行排序
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i++){
            //重复的过滤掉
            if(i>0 && nums[i] == nums[i-1])
                continue;
            Map<Integer,Integer> targetMap = new HashMap<>();
            for(int j=i+1;j<nums.length;j++){
                if(targetMap.containsKey(nums[j])){
                    if(targetMap.get(nums[j]) == 0){
                        resultList.add(Arrays.asList(nums[i],nums[j],-nums[i] - nums[j]));
                        targetMap.put(nums[j],1);
                    }
                }else{
                    targetMap.put(-nums[i] - nums[j],0);
                }
            }
        }
        return resultList;
    }
}

• 时间复杂度：O(n²)
• 时间复杂度：O(n)，因为需要一个额外的哈希表

方法三：遍历数组。

• 首先对数组进行从小到大排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为nums[L] 和nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集

• 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环

• 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过

• 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++

• 当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; // 去重
                    while (L<R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;
    }
}

• 时间复杂度：O(n²)
• 时间复杂度：O(1)