LeetCode刷题记录（哈希表篇）

LeetCode刷题记录（哈希表篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。

[242] Valid Anagram

难度：Easy
语言：C++

题目描述。
题目限定了字符串里字符只能是小写英文字符，因此可以使用长度为26的数组直接当哈希表。若字符串可能包含Unicode字符，则把数组替换成unordered_map使用即可。
若大多数是短字符串，则s一个循环，t一个循环同时检查table[t[i]]是否小于0应该开销更小（两个次数为size的循环）。若大多数是长字符串，那么如下所示的一个循环写table，一个循环检查table应该开销更小（一个次数为size的循环和一个次数为26的循环）。虽然实际上长度超过26的单词应该非常稀有，但作为LeetCode题目，反而应该长字符串的测试用例比较多。

  bool isAnagram(string s, string t) {
    int table[26] = {0};
    int size = s.size();
    if (t.size() != size) {
      return false;
    }
    for (int i = 0; i < size; ++i) {
      table[s[i] - 'a']++;
      table[t[i] - 'a']--;
    }
    for (int i = 0; i < 26; ++i) {
      if (table[i] != 0) {
        return false;
      }
    }
    return true;
  }

[1002] Find Common Characters

难度：Easy
语言：Python

题目描述。
“Easy”题并不Easy。
这道题的特殊点在于字符在结果中是可以重复的。一开始想到的是用一个multimap来做，但是感觉代码会比较麻烦，而且寻思Python也没有multimap的方便替代，于是好奇网上是怎么写的。关键点是为每个word都统计一个hash table，然后再取这些hash table之间的最小值。
用多个hash table取交集（取最小值）的想法确实不容易想到，如果思维被局限于只使用一个hash table，估计会被困扰很久。

    def commonChars(self, words: List[str]) -> List[str]:
        min_count = [0] * 26
        for c in words[0]:
            min_count[ord(c) - ord("a")] += 1

        for word in words[1:]:
            count = [0] * 26
            for c in word:
                count[ord(c) - ord("a")] += 1
            for i, cur in enumerate(min_count):
                min_count[i] = min(cur, count[i])

        ret = []
        for i, num in enumerate(min_count):
            for _ in range(num):
                ret.append(chr(ord("a") + i))
        return ret

[349] Intersection of Two Arrays

难度：Easy
语言：Rust

题目描述。
把第一个array先做成hash set，再把第二个array对着第一个array做成的hash set来查，查完插入返回结果的hash set即可。基本没有难度。

use std::collections::HashSet;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut ret_set: HashSet<i32> = HashSet::with_capacity(1000);
        let mut set1: HashSet<i32> = nums1.into_iter().collect();

        nums2
            .iter()
            .filter(|num| set1.contains(num))
            .for_each(|&num| {
                ret_set.insert(num);
            });

        ret_set.into_iter().collect()
    }
}

[202] Happy Number

难度：Easy
语言：C++

题目描述。
没有难度。就是判断一个数字有没有出现过，用unordered_set即可（set用的是红黑树，unordered_set才是哈希），在此之上又套了一个数学计算的壳子。

class Solution {
 public:
  bool isHappy(int n) {
    unordered_set<int> visited;
    int cur = n;
    while (visited.find(cur) == visited.end()) {
      visited.insert(cur);
      int sum = 0;
      while (cur > 0) {
        sum += (cur % 10) * (cur % 10);
        cur = cur / 10;
      }
      if (sum == 1) {
        return true;
      }
      cur = sum;
    }
    return false;
  }
};

[1] Two Sum

难度：Easy
语言：Python

题目描述。
这道题的核心是只算两个数字的和而不是多个数字，所以一旦扫描到一个数字就能通过差值知道另一个需要的数字是多少。当我们扫描到一个数字，发现对应的另一个数字也已经遇到过了，就说明找到解了。
把num1需要的另一个数字num2作为key，自身num1的index作为value即可使用hash表存储需要的信息。对于遍历到的数字num，先查看当前数字是否在hash表中存在（被遍历过的另一个数字需要），若是则返回hash表对应的value（另一个数字的index）和当前index，否则将target-num与当前index插入hash表。
也可以选择插入的时候用num作为key，然后查找的时候查找target-num，没有什么本质区别。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {}
        for i, num in enumerate(nums):
            if num in hash_table:
                return [hash_table[num], i]
            hash_table[target - num] = i

[454] 4Sum II

难度：Medium
语言：Rust

题目描述。
相比之前的两个数字，这里变为了四个数字，但是分布在四个array里。最坏的情况是暴力遍历一遍，复杂度为 $O(n^4)$ 。这里我们可以把计算内容拆为两半，前两个array的数字两两相加的和放在 $HashMap$ 里，然后后两个array的数字两两相加的和被零减去，再去 $HashMap$ 中查找即可。这样一来，要算的就变成了两个 $n^2$ ，复杂度变为了 $O(n^2)$ 。

use std::collections::HashMap;

impl Solution {
    pub fn four_sum_count(
        nums1: Vec<i32>,
        nums2: Vec<i32>,
        nums3: Vec<i32>,
        nums4: Vec<i32>,
    ) -> i32 {
        let mut map: HashMap<i32, i32> = HashMap::new();
        let mut count = 0;

        for a in &nums1 {
            for b in &nums2 {
                let value = map.entry(a + b).or_insert(0);
                *value += 1;
            }
        }

        for c in &nums3 {
            for d in &nums4 {
                if let Some(value) = map.get(&(0 - (c + d))) {
                    count += value;
                }
            }
        }

        count
    }
}

[383] Ransom Note

难度：Easy
语言：C++

题目描述。
没有难度的题。用第二个字符串做一个哈希表，再拿第一个字符串去查一遍即可。
题目限制了只有英文小写字符。如果是任意字符，把int数组换成使用unordered_map即可。

  bool canConstruct(string ransomNote, string magazine) {
    int umap[26] = {0};
    for (char c : magazine) {
      umap[c - 'a']++;
    }

    for (char c : ransomNote) {
      umap[c - 'a']--;
      if (umap[c - 'a'] < 0) {
        return false;
      }
    }

    return true;
  }

[15] 3Sum

难度：Medium
语言：Python

题目描述。
不太好做的一道题。咋一看只要把两个数字的和算出来，再拿第三个数字查哈希就可以，但实际上这道题要求要去重，而这个去重就是难度的来源。
可以把题目要求的去重理解成两个维度：

同一个index位置的数字不能在一个3 sum中使用两次（但是输入是可能有重复的数字的，也就是说某数字在输入中有几个重复的，该数字在一次求和中就最多只能用几次）
结果中的顺序是无所谓的，也就是说[0, 1, -1]和[0, -1, 1]是一样的，因此顺序不同导致的结果重复也要去掉。

由此，可得到如下代码。
解法的关键在于对list做了排序，这样一来同样的数字就会被排列到一起，方便做去重。
首先，j从i+1开始，n3的index又要求大于j，防止了选择同一index位置的元素，避免出现第一种重复。n1==nums[i-1]和n2=nums[j-1]时的跳过避免了出现同样的解（通过n1不选重复选过的数字，n2也不选重复选过的数字），最后n1，n2和n3的index严格有序保证了不出现顺序打乱出现的重复。
另外，最后的early stop是源于，数组是排过序的，而n3又是从0 - n1 - n2得到。在第二个循环中，n2不断递增，因此n3严格减小。如果某一时刻n3的index小于n2，那么后面n3的index也都会一直小于n2，也就没必要再算了，可以提前退出。
实际上，这道题网上更广泛的解法是使用双指针，可参考这篇solution。其如果用哈希表来做会比较麻烦。但是在本人所看的刷题攻略中，这道题被放在了哈希表部分，所以就当用来锻炼了。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        num_table = {}
        res = []
        nums.sort()
        for i, n in enumerate(nums):
            num_table[n] = i

        for i, n1 in enumerate(nums):
            if i > 0 and n1 == nums[i - 1]:
                continue
            for j, n2 in enumerate(nums[i + 1 :], i + 1):
                if j > i + 1 and n2 == nums[j - 1]:
                    continue
                n3 = 0 - n1 - n2
                if n3 in num_table:
                    if num_table[n3] > j:
                        res.append([n1, n2, n3])
                    else:
                        # Early stop
                        break

        return res

[18] 4Sum

难度：Medium
语言： Rust

题目描述。
相比3Sum只是多了一层循环，其他没有太大区别。中间转成64位是为了防止溢出。
此外，这道题同样可以（并更推荐）使用双指针法来做。

use std::collections::HashMap;

impl Solution {
    pub fn four_sum(nums: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut nums = nums;
        let mut num_table: HashMap<i32, usize> = HashMap::new();
        let mut res: Vec<Vec<i32>> = Vec::new();
        let len = nums.len();
        nums.sort();
        for (i, n) in nums.iter().enumerate() {
            num_table.insert(*n, i);
        }

        for i in 0..len {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            for j in i + 1..len {
                if j > i + 1 && nums[j] == nums[j - 1] {
                    continue;
                }
                for k in j + 1..len {
                    if k > j + 1 && nums[k] == nums[k - 1] {
                        continue;
                    }
                    let n = target as i64 - nums[i] as i64 - nums[j] as i64 - nums[k] as i64;
                    if n < i32::MIN as i64 || n > i32::MAX as i64 {
                        continue;
                    }
                    let n = n as i32;
                    if num_table.contains_key(&n) {
                        if *num_table.get(&n).unwrap() > k {
                            res.push(vec![nums[i], nums[j], nums[k], n]);
                        } else {
                            break;
                        }
                    }
                }
            }
        }

        return res;
    }
}

总结

只需要key，可以使用set；同时需要key和value，可使用map。
其中C++只有std::unordered_map和std::unordered_set底层是哈希实现，其他的例如std::map是红黑树实现，key是有序的，且查询、增删效率是 $O(log n)$ 而不是 $O(1)$ 。
如果key的范围很小，数量也不多且固定，可以考虑使用数组作为哈希表，例如用长度为26的数组表示所有的英文小写字母，以节省开销。更复杂的场景则使用标准库中的类型即可。
部分题目比较简单，也有些题目有不好想到的内容，例如：

[1002] Find Common Characters使用了多个哈希表而不是一个哈希表。
有一些“NSum”类的题，比较相似又各有区别。[1] Two Sum因为只会有一个答案，所以只要查一遍即可。[454] 4Sum II需要前两个数组做一个哈希表，后两个数组再去查，把 $O(n^4)$ 变成了两个 $O(n^2)$ ，又因为四个数组来自四个不同的数组，所以不用考虑去重的问题。而[15] 3Sum的数组来自同一个数组，所以需要考虑到同样的value，但是打乱顺序的重复问题。[18] 4Sum则只是在3Sum上面多包了一层，无本质区别。

AllenY's blog