AllenY's blog

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

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

1. 同一个index位置的数字不能在一个3 sum中使用两次（但是输入是可能有重复的数字的，也就是说某数字在输入中有几个重复的，该数字在一次求和中就最多只能用几次）
2. 结果中的顺序是无所谓的，也就是说[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的数组表示所有的英文小写字母，以节省开销。更复杂的场景则使用标准库中的类型即可。
部分题目比较简单，也有些题目有不好想到的内容，例如：

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

补充

[49] Group Anagrams

难度：Medium
语言：C++

题目描述。
想一种方式给同一组字母异位词分配一个key即可。

• 可以使用排序的方式，因此同一组字母异位词排序后的结果是相同的，见generateSortKey。
• 可以使用计数的方式，计算str中每个字符出现的次数，见generateCountKey。

class Solution {
  public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> map;
        for (string str : strs) {
            // string key = generateCountKey(str);
            string key = generateSortKey(str);
            map[key].emplace_back(str);
        }

        vector<vector<string>> res;
        for (pair<string, vector<string>> item : map) {
            res.emplace_back(item.second);
        }
        return res;
    }

    string generateCountKey(string str) {
        int count[26] = {0};
        for (char c : str) {
            count[c - 'a'] += 1;
        }
        string key = "";
        for (int i = 0; i < 26; ++i) {
            key += 'a' + i;
            key += count[i];
        }
        return key;
    }

    string generateSortKey(string str) {
        sort(str.begin(), str.end());
        return str;
    }
};

[128] Longest Consecutive Sequence

难度：Medium
语言：C++

题目描述。
使用了unordered_set来存储并快速查询某个数字是否存在。
这道题的关键在于num-1，即查询当前数字的上一个数字是否存在，若不存在则说明当前数字是一个连续序列的开头。此时开始查询num+i是否存在，并更新最长序列长度longestLength。若num-1存在，则跳过当前数字即可。

class Solution {
  public:
    int longestConsecutive(vector<int> &nums) {
        unordered_set<int> numSet;
        for (const int &num : nums) {
            numSet.insert(num);
        }
        int longestLength = 0;
        for (const int &num : numSet) {
            if (numSet.find(num - 1) == numSet.end()) {
                int i = 1;
                while (numSet.find(num + i) != numSet.end()) {
                    ++i;
                }
                longestLength = max(longestLength, i);
            }
        }
        return longestLength;
    }
};

[438] Find All Anagrams in a String

难度：Medium
语言：C++

题目描述。
Naive的方式是为s的固定长度滑动窗口维护一个哈希表，再和p的哈希表对比是否一样即可。这样做是能通过测试的。
但我们应该稍微有点追求，不用这么Naive的方式。事实上我们只需要维护一个哈希表cmap再加一个变量diff。cmap存储了各字符在滑动窗口和p中的数量差异情况（value小于0说明该字符在p中更多，大于0说明该字符在滑动窗口中更多，等于0说明一样多）；diff则记录cmap中value不为0的字符种类的数量。即，如果diff == 0，说明cmap中所有字符的value都为0，说明当前滑动窗口的里就是p的anagram。

class Solution {
  public:
    vector<int> findAnagrams(string s, string p) {
        int pn = p.size();
        int sn = s.size();
        vector<int> res;
        if (sn < pn) {
            return res;
        }
        int diff = 0;
        unordered_map<char, int> cmap;
        for (int i = 0; i < pn; ++i) {
            --cmap[p[i]];
            ++cmap[s[i]];
        }
        for (auto item : cmap) {
            if (item.second != 0) {
                ++diff;
            }
        }
        if (diff == 0) {
            res.emplace_back(0);
        }

        for (int i = 0; i < sn - pn; ++i) {
            // remove s[i] from the window
            if (cmap[s[i]] == 1) {
                --diff;
            } else if (cmap[s[i]] == 0) {
                ++diff;
            }
            cmap[s[i]] -= 1;

            // add s[i+pn] to the window
            if (cmap[s[i + pn]] == -1) {
                --diff;
            } else if (cmap[s[i + pn]] == 0) {
                ++diff;
            }
            cmap[s[i + pn]] += 1;

            if (diff == 0) {
                res.emplace_back(i + 1);
            }
        }

        return res;
    }
};

[560] Subarray Sum Equals K

难度：Meidum
语言：C++

题目描述。、
题目要找到连续的子数组使和为k。解题核心在于，我们使用两个前缀和的差来代表了一段子串的和。
实际上，我们只需要记录终点为每个位置$i$的前缀和pre[i]（从nums[0]加到nums[i]的和）即可，则$(j, i]$这部分的子串和就是pre[i] - pre[j]。于是若有pre[i] - pre[j] == k存在，就说明存在有$(j, i]$这么一段子串的和为k，满足题意。
我们使用哈希表smap来存储前缀和的出现情况（key为前缀和的值，value为前缀和的出现次数）。当我们遍历到i的时候，查一下smap[pre[i] - k]是否存在。若存在，说明有j使pre[i] - k == pre[j]即pre[i] - pre[j] == k。我们让最终结果count加上这个前缀和smap[pre[i] - k]出现的次数即可。又因为前缀和没必要使用数组来存，我们只需要每次累加得到当前位置的前缀和，因此只用一个int变量pre存储前缀和即可。

class Solution {
  public:
    int subarraySum(vector<int> &nums, int k) {
        unordered_map<int, int> smap;
        int pre = 0, count = 0;
        smap[0] = 1;
        for (int &num : nums) {
            pre += num;
            if (smap.find(pre - k) != smap.end()) {
                count += smap[pre - k];
            }
            smap[pre] += 1;
        }
        return count;
    }
};

[76] Minimum Window Substring

难度：Hard
语言：C++

题目描述。
使用滑动窗口即可。移动右边界使滑动窗口满足“包含t中所有字符（含数量）”的条件，在此基础上再尽可能移动左边界来缩小滑动窗口即可。
这里代码上使用了和[438] Find All Anagrams in a String一样的优化。即，我们不分别使用两个哈希表来记录滑动窗口和t中的字符出现情况，而是只使用一个哈希表cmap来记录两者之间的字符差异情况，又用变量lack记录整体的差异情况（lack == 0说明滑动窗口已经包含了所有t中字符（含重复））。
cmap[c]小于0说明t中字符c还未被滑动窗口覆盖。当cmap[c]从-1转为0时说明t中出现过的某个字符c（含数量）此时被滑动窗口涵盖了，此时我们使lack减一。

class Solution {
  public:
    string minWindow(string s, string t) {
        unordered_map<char, int> cmap;
        int tn = t.size(), sn = s.size();
        int lack = 0;
        int minLenth = __INT_MAX__, minIndex = 0;

        for (int i = 0; i < tn; ++i) {
            --cmap[t[i]];
        }

        lack = cmap.size();

        for (int left = 0, right = 0; right < sn; ++right) {
            if (++cmap[s[right]] == 0) {
                --lack;
            }
            while (cmap[s[left]] > 0) {
                --cmap[s[left]];
                ++left;
            }
            if (lack <= 0 && right - left + 1 < minLenth) {
                minLenth = right - left + 1;
                minIndex = left;
            }
        }

        return minLenth == __INT_MAX__ ? "" : s.substr(minIndex, minLenth);
    }
};