带你拿捏哈希表

向Carl老师学习，用最简单的话，讲述最复杂的知识。( •̀ ω •́ )✧

什么是哈希表？

灵魂一问，这是正常人看到后，都会产生的疑问，就好比你是谁。

初学者可以将其看成一个数组！

大家都知道数组是怎么存数据的！

通过下标(0~N，是一串连续的数字)，将对应数据为其赋值。

哈希表大致就是这样存储的。

既然如此，那为啥它不叫数组，而叫哈希表(⊙_⊙)？

因为哈希表计算计算下标的时候，是通过一个名为 哈希函数 的工具，将key值(也就是输入内容，字符串也好，数字也好) 通通转化为一个特定的下标。而这个被计算出来的数据，功能就相当于数组中的下标！

（哈希表就是数组的拓展。也就是说，若没有数组，自然也就没有哈希表！）

为什么需要哈希表？

看到这，那肯定有人要问，哈希表 取个下标还要计算，多么麻烦呐？为啥不用数组？

假如我们有一组数据,某位工程师每年某个月的收入情况

2017年1月 -- 10000 2018年2月 -- 13000 2019年4月 -- 14000 2020年12月 -- 20000

你拿数组怎么存？

怎么存？

在上方说过，你可以通过哈希函数(hashFunction)，将他们转化为特定的数字。

2017年1月 --> 11 2018年2月 --> 13 2019年4月 --> 14 2020年12月 --> 20

这样就能直接实现存入。

反过来操作，就能实现查找！完美的实现了时间复杂度为O(1)的操作。 

存在了一起怎么办？

思维严密的人，在看到这种通过计算，而得出的下标时，肯定会有疑惑！

万一计算出了相同的下标怎么办？

这里就涉及到了哈希碰撞，就是计算结果相同。

其实现在有多种解决方案，而在本篇博客中，主要详细讲解两种方法。

拉链法

想必链表大家都学过了，当你遇到这种问题时，如图

这样通过索引，就能链接下标相同，但是数值不同的数据。

线性探测法

这个就是当两个下标相同时，自动往后移动，直到遇到空位。图片

常见的3种哈希结构

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

1、数组

这里就不多说了，想必大家都懂。

2、set(集合)

官方主要有3种，set，multiset，unordered_set。

在这里，先说unordered_set，unordered_set的底层，就是咱们上述所说的哈希表。查询速率为O(1)，基础用法。

#include <iostream> #include <unordered_set> using namespace std; int main(){ // 构建 unordered_set<int> uset; // 增 uset.insert(3); // 删 uset.erase(3); uset.clear(); // 查 int size = uset.size(); bool isEmpty = uset.empty(); for(auto it = uset.begin(); it!=uset.end(); ++it){ cout<<*it<<endl; } for(int i:uset) cout<<i<<endl; return 0; }

其中，set与multiset的底层实现是红黑树，可能大家现在对“红黑树”还不够了解，只需知道，这俩底层不是用哈希表实现的就行，自然查询速率也就不是O(1)，而是O(log N)，这里就不做详细的解释啦。

3、map(映射)

同样大致也只有这3种，跟set其实相差不大。

map(映射)，也主要分为map、multimap、unordered_map。

咱们这里也先说unordered_map，他的底层同unordered_set一样是哈希表。

#include <iostream> #include <unordered_map> using namespace std; int main(){ // 默认构造 unordered_map<int,int> umap; // 构造并初始化 unordered_map<int,string> myMap1 = {{1,"one"},{2,"two"}}; // 构造并指定初始容量 unordered_map<int,string> myMap2(10); // 构造，并直接复制 unordered_map<int,string> myMap3 = myMap2; // 插入 myMap2.insert({2,"2"}); // 访问 cout<<myMap2[2]; // 删除 myMap2.erase(2); // 查找元素 auto it = myMap2.find(2); if(it!=myMap2.end()){ cout<<"存在改元素"<<endl; } return 0; }

map、multimap底层都是红黑数结构。与set集合相似。

当然，知识永远只是知识。唯有经题目磨练才会变得更加锋利。

大纲

-- 基础练习 -- 

一、有效的字母异位词-（解析）-运用数组，这种最基本的哈希表

二、 两个数组的交集-（解析）-巧妙运用数组的合并

三、快乐数-（解析）-运用stl库

四、两数之和-（解析）-运用哈希表查找，解决两数相加

五、四数相加 II-（解析）-双指针解决两数相加

六、赎金信-（解析）-巧妙运用数组

七、三数之和-（解析）-高配版两数之和(双指针)

八、四数之和-（解析）-高配版三数之和(双指针)

-- 蓝桥真题 --

一、字符统计-（解析）-数组代替哈希表

二、连连看-（解析）-数学坐标知识，用坐标相加，模拟斜率相同的思维

三、团建-（解析）-暴力深搜dfs

四、k倍区间-（解析）-前缀和取模，模拟区间倍数，结合公式推断。

( •̀ ω •́ )✧点击这里，继续学习其他模块吧！

题目

--  基础练习 --

一、有效的字母异位词

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



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

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

提示:1 <= s.length, t.length <= 5 * 104s 和 t 仅包含小写字母



进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

class Solution { // 突兀的发现数组神通广大，是简单的哈希表，并且能手撕链表 // 不是天才写不出来 public: bool isAnagram(string s, string t) { // 数组就是最简单的哈希表 int res[26]={0}; // 初始化 for(char c:s) res[c-'a']++; for(char c:t) res[c-'a']--; for(int i:res) if(i!=0) return false; return true; /* unordered_map<char,int> uMap; for(char c:s) uMap[c]++; for(char c:t){ // 判断是否存在 if(uMap.find(c)==uMap.end()) return false; uMap[c]--; } for(auto it=uMap.begin(); it!=uMap.end(); ++it){ if(it->second!=0) return false; } return true; */ } };

二、 两个数组的交集

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



示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]

示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的



提示：1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000

class Solution { // 数组替代哈希 public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // 用数组代替哈希 vector<int> res; int res1[1005]={},res2[1005]={}; for(int i:nums1) res1[i]++; for(int i:nums2) res2[i]++; for(int i=0; i<1005; ++i){ if(res1[i]!=0&&res2[i]!=0) res.push_back(i); } return res; } };

三、快乐数

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

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。



示例 1：输入：n = 19 输出：true 解释： 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1

示例 2：输入：n = 2 输出：false

提示：1 <= n <= 231 - 1

class Solution { // 这就是熟练运用stl库的好处，我爱你攀拓 public: bool isHappy(int n) { unordered_set<int> set; string str; while(1){ str = to_string(n); n = 0; for(char c : str) n+=(int)pow(c-'0',2); // cmath if(n==1) return true; else{ if(set.find(n)!=set.end()) return false; set.insert(n); } } } };

四、两数之和

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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



示例 1：输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：输入：nums = [3,2,4], target = 6 输出：[1,2]

示例 3：输入：nums = [3,3], target = 6 输出：[0,1]

提示：2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个有效答案



进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

class Solution { // 本题能用multimap来做，更能用unordered来做; public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int,int> umap; for(int i=0; i<nums.size(); ++i){ int num = target-nums[i]; auto it = umap.find(num); if(it!=umap.end()) return vector<int>{i,it->second}; umap.insert({nums[i],i}); } /* // 问题就是我不会这个，数值 multimap<int,int> mmap; for(int i=0; i<nums.size(); ++i) mmap.insert({nums[i],i}); // 插入 // 将所有数据插入其中 for(int i=0; i<nums.size(); ++i){ // 从头开始判断 int num = target - nums[i]; // 取值 auto it = mmap.find(num); // 存入数据 while(it != mmap.end()&&it->first==num){ if(it->second!=i) return vector<int>{i,it->second}; ++it; } } return vector<int>(0); */ return vector<int>(0); } };

五、四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:A = [ 1, 2]B = [-2,-1]C = [-1, 2]D = [ 0, 2]

输出:

2

解释:

两个元组如下:(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

class Solution { // 拆分思想很好 public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { int flag = 0; unordered_map<int,int> umap; for(int i:nums1){ for(int j:nums2){ umap[i+j]++; } } for(int i:nums3){ for(int j:nums4){ int num = -i-j; auto it = umap.find(num); if(it!=umap.end()) flag+=it->second; } } return flag; } };

六、赎金信

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

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

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



示例 1：输入：ransomNote = "a", magazine = "b" 输出：false

示例 2：输入：ransomNote = "aa", magazine = "ab" 输出：false

示例 3：输入：ransomNote = "aa", magazine = "aab" 输出：true

提示：1 <= ransomNote.length, magazine.length <= 105ransomNote 和 magazine 由小写英文字母组成

class Solution { // 数组模拟了一把，哈希表 public: bool canConstruct(string ransomNote, string magazine) { int res[26]={0}; for(char c:magazine){ res[c-'a']++; } for(char c:ransomNote){ res[c-'a']--; } for(int i:res){ if(i<0){ return false; } } return true; } }; 

七、三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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



示例 1：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

示例 3：输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。



提示：3 <= nums.length <= 3000-105 <= nums[i] <= 105

class Solution { // 试问，如何将其做出来 // 双指针？二数之和？ !! public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; sort(nums.begin(),nums.end()); for(int i=0; i<nums.size(); ++i){ if(i>0&&nums[i]==nums[i-1]) continue; int sum = 0-nums[i]; int l = i+1, r = nums.size()-1; while(l<r){ // 看多了自己，会变得自恋 if(l>i+1&&nums[l]==nums[l-1]){ l++; continue; } if(r<nums.size()-1 && nums[r+1]==nums[r]){ r--; continue; } if(nums[r]+nums[l]<sum){ l++; }else if(nums[r]+nums[l]>sum){ r--; }else{ res.push_back(vector<int>{nums[i],nums[l],nums[r]}); l++; r--; } } } return res; /* vector<vector<int>> res; sort(nums.begin(),nums.end()); for(int i=0; i<nums.size(); ++i){ // 屏障 if(nums[i]>0) break; // 直接结束 if( i>0&&nums[i-1]==nums[i]) continue; // 两数判断 unordered_set<int> uset; for(int j=i+2; j<nums.size(); ++j){ uset.insert(nums[j-1]); // 方向别搞错了 if(j>i+2&&nums[j-1]==nums[j]&&nums[j-2]==nums[j-1]) continue; // 连续3个相同 int num = 0-nums[i]-nums[j]; auto it = uset.find(num); if(it!=uset.end()){ res.push_back(vector<int>{nums[i],nums[j],*it}); uset.erase(num); // 代表已经用过了 } } } return res; */ } };

八、四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：0 <= a, b, c, d < na、b、c 和 d 互不相同nums[a] + nums[b] + nums[c] + nums[d] == target

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



示例 1：输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示：1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109

class Solution { // 巧妙运用双指针 public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; sort(nums.begin(),nums.end()); for(int i=0; i<nums.size(); ++i){ if(i>0&&nums[i]==nums[i-1]) continue; for(int j=i+1; j<nums.size(); ++j){ if(j>i+1&&nums[j-1]==nums[j]) continue; int l = j+1, r = nums.size()-1; long long sum = (long long)target-nums[i]-nums[j]; while(l<r){ if(l>j+1&&nums[l-1]==nums[l]){ l++; continue; } if(r<nums.size()-1&&nums[r+1]==nums[r]){ r--; continue; } long long s_num = (long long)nums[r]+nums[l]; if(s_num>sum){ r--; continue; }else if(s_num<sum){ l++; continue; }else{ res.push_back(vector<int>{nums[i],nums[j],nums[l],nums[r]}); r--; l++; } } } } return res; } };

-- 蓝桥真题 --

一、字符统计

问题描述

给定一个只包含大写字母的字符串 SS, 请你输出其中出现次数最多的字符。

如果有多个字母均出现了最多次, 按字母表顺序依次输出所有这些字母。

输入格式

一个只包含大写字母的字等串 SS.

输出格式

若干个大写字母，代表答案。

样例输入



样例输出

评测用例规模与约定

对于 100%100% 的评测用例, 1≤∣S∣≤1061≤∣S∣≤106.

运行限制最大运行时间：1s最大运行内存: 512M

Java版

import java.util.Scanner; public class Main { public static void main(String[] args) { // 用于存储每个字母出现的次数，初始值都为 0 int[] res = new int[26]; // 创建 Scanner 对象用于读取用户输入 Scanner scanner = new Scanner(System.in); // 读取用户输入的字符串 String str = scanner.next(); // 遍历字符串中的每个字符 for (char c : str.toCharArray()) { // 计算字符在数组中的索引并增加对应计数 res[c - 'A']++; } // 用于记录出现次数最多的字母的出现次数 int maxNum = 0; // 遍历数组，找出出现次数最多的字母的出现次数 for (int i : res) { maxNum = Math.max(maxNum, i); } // 遍历数组，找出出现次数等于最大次数的字母并输出 for (int i = 0; i < 26; i++) { if (res[i] == maxNum) { System.out.print((char) (i + 'A')); } } // 关闭 Scanner 对象 scanner.close(); } }

C++版

#include <iostream> using namespace std; // 简单运用哈希表 int main() { int res[26]={0}; string str; cin>>str; for(char c : str){ res[c-'A']++; } int max_num=0; for(int i:res) max_num = max(max_num,i); for(int i=0; i<26; ++i){ if(res[i]==max_num) cout<<char(i+'A'); } return 0; }

二、连连看

问题描述

小蓝正在和朋友们玩一种新的连连看游戏。在一个 n×mn×m 的矩形网格中，每个格子中都有一个整数，第 ii 行第 jj 列上的整数为 Ai,jAi,j​ 。玩家需要在这个网格中寻找一对格子 (a,b)−(c,d)(a,b)−(c,d) 使得这两个格子中的整数 Aa,bAa,b​ 和 Ac,dAc,d​ 相等，且它们的位置满足 ∣a−c∣=∣b−d∣>0∣a−c∣=∣b−d∣>0 。请问在这个 n×mn×m 的矩形网格中有多少对这样的格子满足条件。

输入格式

输入的第一行包含两个正整数 n,mn,m，用一个空格分隔。

接下来 nn 行，第 ii 行包含 mm 个正整数 Ai,1,Ai,2,⋯,Ai,mAi,1​,Ai,2​,⋯,Ai,m​，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

样例输出



样例输出



样例说明

一共有以下 66 对格子：(1,2)−(2,1)(1,2)−(2,1)，(2,2)−(3,1)(2,2)−(3,1)，(2,1)−(3,2)(2,1)−(3,2)，(2,1)−(1,2)(2,1)−(1,2)，(3,1)−(2,2)(3,1)−(2,2)，(3,2)−(2,1)(3,2)−(2,1)。

评测用例规模与约定

对于 20%20% 的评测用例，1≤n,m≤501≤n,m≤50；

对于所有评测用例，1≤n,m≤1000,1≤Ai,j≤10001≤n,m≤1000,1≤Ai,j​≤1000。

Java版

某个路人给出的很酷的解析 ''' (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,2) (1,3) (1,4) (2,0) (2,1) (2,2) (2,3) (2,4) (3,0) (3,1) (3,2) (3,3) (3,4) 假设右对角线是 (左下) -> (右上) (1,0) (0,1)是一对 (2,0) (1,1) (0,2)是一对 (3,0) (2,1) (1,2) (0,3) 是一对 不难发现，这类右对角线中坐标(i,j) i + j 为一个定值 假设左对角线是 (左上) -> (右下) (0,3) (1,4)是一对 (0,2) (1,3) (2,4)是一对 (0,1) (1,2) (2,3) (3,4)是一对 不难发现，这类左对角线中坐标(i,j) i - j 为一个定值 因此 当我们遍历到一个坐标(i,j)时 需要找到之前 左右对角线 有多少个和当前坐标(i,j)值一样的 需要用一个哈希记录一下到当前位置为止，左右对角线中某个值x已经出现了多少次 累加一下 因为要求坐标对数 (1,2) -> (2,1) 和 (2,1) -> (1,2) 算两个答案 所以最后答案 * 2 可能有朋友不清楚python中的Counter和defaultdict是干什么的 这两个类似于基础语法中学的字典，具有键值对的性质 这两个一般来说没什么区别，习惯哪个用哪个 比起普通的字典， 如Counter(a)可以直接对列表里元素出现次数进行计数，简洁一点 而且会给没出现的元素赋值为0，避免像字典一样取到不存在的值会报错 当然，分别用一个二维数组计数也可以，如果Aij的值到达了1e9就不可用数组了哦~ 看到这里觉得有用就点个赞呗！！！ >< ''' import java.util.Scanner; public class Main { public static void main(String[] args) { // 创建一个 Scanner 对象用于读取用户输入 Scanner scanner = new Scanner(System.in); // 定义矩阵的行数 n 和列数 m int n, m; // 读取用户输入的行数 n 和列数 m n = scanner.nextInt(); m = scanner.nextInt(); // 定义一个二维数组 arr 用于存储矩阵元素 int[][] arr = new int[1005][1005]; // 定义两个二维数组 cur1 和 cur2 分别用于记录反对角线和正对角线上每个数字的出现次数 int[][] cur1 = new int[2005][1005]; int[][] cur2 = new int[2005][1005]; // 读取矩阵元素 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { // 读取矩阵中第 i 行第 j 列的元素 arr[i][j] = scanner.nextInt(); } } // 初始化满足条件的格子对数量为 0 int ans = 0; // 遍历矩阵中的每个元素 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { // 累加当前元素在反对角线和正对角线上与它数字相同的格子数量到 ans 中 ans += cur1[i - j + 1000][arr[i][j]] + cur2[i + j][arr[i][j]]; // 更新反对角线上当前数字的出现次数 cur1[i - j + 1000][arr[i][j]]++; // 更新正对角线上当前数字的出现次数 cur2[i + j][arr[i][j]]++; } } // 由于每一对格子会被重复计算两次，所以最终答案要乘以 2 System.out.println(ans * 2); // 关闭 Scanner 对象 scanner.close(); } }

C++版

#include <iostream> using namespace std; // 根据性质 // 对角线的性质 int arr[1005][1005],cur1[2005][1005],cur2[2005][1005]; // cur1(左上->右下) cur2(右上->左下) int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cin >> arr[i][j]; int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { ans += cur1[i - j + 1000][arr[i][j]] + cur2[i + j][arr[i][j]]; cur1[i - j + 1000][arr[i][j]]++; cur2[i + j][arr[i][j]]++; } } cout<<ans*2<<endl; } // 暴力枚举法 /* #include <iostream> #include <unordered_map> #include <vector> #include <cmath> using namespace std; // 暴力枚举 int main() { int n,m; cin>>n>>m; unordered_map<int,vector<pair<int,int>>> umap; int cur; for(int i=1; i<=n; ++i){ for(int j=1; j<=m; ++j){ cin>>cur; umap[cur].push_back(pair<int,int>(i,j)); } } int count = 0; // 暴力枚举 for(auto it = umap.begin(); it!=umap.end(); ++it){ vector<pair<int,int>>& vec = it->second; // 获得值 int cur_count = 0; for(int i=0; i<vec.size(); ++i){ for(int j=i+1; j<vec.size(); ++j){ // 枝剪操作要到位 int ac = fabs(vec[i].first-vec[j].first); int bd = fabs(vec[i].second-vec[j].second); if(ac==bd){ // 不是同一个点 cur_count++; } } } count+=cur_count*2; } cout<<count<<endl; return 0; } */

三、团建

问题描述

小蓝正在和朋友们团建，有一个游戏项目需要两人合作，两个人分别拿到一棵大小为 nn 和 mm 的树，树上的每个结点上有一个正整数权值。

两个人需要从各自树的根结点 1 出发走向某个叶结点，从根到这个叶结点的路径上经过的所有结点上的权值构成了一个正整数序列，两人的序列的最长公共前缀即为他们的得分。给出两棵树，请计算两个人最多的得分是多少。

输入格式

输入的第一行包含两个正整数 n,mn,m，用一个空格分隔。

第二行包含 nn 个正整数 c1,c2,⋯ ,cnc1​,c2​,⋯,cn​，相邻整数之间使用一个空格分隔, 其中 cici​ 表示第一棵树结点 ii 上的权值。

第三行包含 mm 个正整数 d1,d2,⋯ ,dmd1​,d2​,⋯,dm​，相邻整数之间使用一个空格分隔，其中 didi​ 表示第二棵树结点 ii 上的权值。

接下来 n−1n−1 行，每行包含两个正整数 ui,viui​,vi​ 表示第一棵树中包含一条 uiui​ 和 vivi​ 之间的边。

接下来 m−1m−1 行，每行包含两个正整数 pi,qipi​,qi​ 表示第二棵树中包含一条 pipi​ 和 qiqi​ 之间的边。

输出格式

输出一行包含一个整数表示答案。

样例输入1



样例输出1



样例输入2



样例输出2



样例说明

在第一个样例中，两个序列可以为 [10,20],[10,30][10,20],[10,30] ，最大前缀为 11;

在第二个样例中，两个序列可以为 [10,20,40],[10,20,30][10,20,40],[10,20,30] ，最大前缀为 22。

评测用例规模与约定

对于 20%20% 的评测用例， 1≤n,m≤5001≤n,m≤500 ;

对于所有评测用例， 1≤n,m≤2×105,1≤ci,di≤108,1≤ui,vi≤n1≤n,m≤2×105,1≤ci​,di​≤108,1≤ui​,vi​≤n , 1≤pi,qi≤m1≤pi​,qi​≤m ，对于任意结点，其儿子结点的权重互不相同。

Java版

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Scanner; public class Main { // 定义一个常量 NUM，用于表示数组的最大长度，这里设置为 200005 static final int NUM = 200005; // 用来存储第一棵树每个节点的值，数组下标对应节点编号 static long[] nArr = new long[NUM]; // 用来存储第二棵树每个节点的值，数组下标对应节点编号 static long[] mArr = new long[NUM]; // 记录两棵树中对应节点值相等的最长路径长度，初始化为 0 static int maxCount = 0; // 存储第一棵树的邻接表，键是节点编号，值是该节点的所有邻居节点组成的列表 static Map<Integer, List<Integer>> nUmap = new HashMap<>(); // 存储第二棵树的邻接表，键是节点编号，值是该节点的所有邻居节点组成的列表 static Map<Integer, List<Integer>> mUmap = new HashMap<>(); /** * 深度优先搜索方法，用于递归地比较两棵树中对应节点的值，找出最长匹配路径 * @param a 第一棵树中的当前节点编号 * @param b 第二棵树中的当前节点编号 * @param cur 当前已经匹配的路径长度 */ static void dfs(int a, int b, int cur) { // 如果当前两棵树中对应节点的值不相等，说明路径匹配中断，直接返回 if (nArr[a] != mArr[b]) { return; } // 当前匹配的路径长度加 1 cur = cur + 1; // 更新最大匹配路径长度，如果当前路径长度比之前记录的最大长度大，则更新 if (cur > maxCount) { maxCount = cur; } // 获取第一棵树中节点 a 的所有邻居节点，如果该节点没有邻居，就创建一个空列表 List<Integer> nNeighbors = nUmap.get(a); if (nNeighbors == null) { nNeighbors = new ArrayList<>(); } // 获取第二棵树中节点 b 的所有邻居节点，如果该节点没有邻居，就创建一个空列表 List<Integer> mNeighbors = mUmap.get(b); if (mNeighbors == null) { mNeighbors = new ArrayList<>(); } // 遍历第一棵树中节点 a 的所有邻居节点 for (int i = 0; i < nNeighbors.size(); i++) { // 获取当前邻居节点的编号 int neighborA = nNeighbors.get(i); // 遍历第二棵树中节点 b 的所有邻居节点 for (int j = 0; j < mNeighbors.size(); j++) { // 获取当前邻居节点的编号 int neighborB = mNeighbors.get(j); // 递归调用 dfs 方法，继续比较这两个邻居节点及其子节点的匹配情况 dfs(neighborA, neighborB, cur); } } } public static void main(String[] args) { // 创建一个 Scanner 对象，用于从标准输入读取数据 Scanner scanner = new Scanner(System.in); // 读取第一棵树的节点数量 int n = scanner.nextInt(); // 读取第二棵树的节点数量 int m = scanner.nextInt(); // 读取第一棵树每个节点的值，并存储到 nArr 数组中 for (int i = 1; i <= n; i++) { nArr[i] = scanner.nextLong(); } // 读取第二棵树每个节点的值，并存储到 mArr 数组中 for (int j = 1; j <= m; j++) { mArr[j] = scanner.nextLong(); } // 读取第一棵树的边信息，构建邻接表 for (int i = 0; i < n - 1; i++) { // 读取边的起点 int l = scanner.nextInt(); // 读取边的终点 int r = scanner.nextInt(); // 如果邻接表中还没有这个起点节点的记录，就创建一个新的列表 if (!nUmap.containsKey(l)) { nUmap.put(l, new ArrayList<>()); } // 将终点节点添加到起点节点的邻居列表中 nUmap.get(l).add(r); } // 读取第二棵树的边信息，构建邻接表 for (int i = 0; i < m - 1; i++) { // 读取边的起点 int l = scanner.nextInt(); // 读取边的终点 int r = scanner.nextInt(); // 如果邻接表中还没有这个起点节点的记录，就创建一个新的列表 if (!mUmap.containsKey(l)) { mUmap.put(l, new ArrayList<>()); } // 将终点节点添加到起点节点的邻居列表中 mUmap.get(l).add(r); } // 从两棵树的根节点（编号为 1）开始进行深度优先搜索，初始路径长度为 0 dfs(1, 1, 0); // 输出找到的最大匹配路径长度 System.out.println(maxCount); // 关闭 Scanner 对象，释放资源 scanner.close(); } } 

C++版 

#include <iostream> #include <unordered_map> #include <vector> #define ll long long const int num = 2e5+5; ll n_arr[num]; ll m_arr[num]; using namespace std; // 暴力深搜 int count = 0; unordered_map<int,vector<int>> n_umap; unordered_map<int,vector<int>> m_umap; // 开启深搜模式 void dfs(int a, int b, int cur){ // tmd 你还真暴力呐 if(n_arr[a]!=m_arr[b]) return; // 直接结束 cur += 1; count = max(count,cur); // 增加 for(int i=0; i<n_umap[a].size(); ++i){ for(int j=0; j<m_umap[b].size(); ++j){ dfs(n_umap[a][i],m_umap[b][j],cur); } } } int main(){ int n,m; cin>>n>>m; for(int i=1; i<=n; ++i) cin>>n_arr[i]; for(int j=1; j<=m; ++j) cin>>m_arr[j]; int l,r; for(int i=0; i<n-1; ++i){ cin>>l>>r; n_umap[l].push_back(r); } for(int i=0; i<m-1; ++i){ cin>>l>>r; m_umap[l].push_back(r); } dfs(1,1,0); cout<<count<<endl; return 0; }

四、k倍区间

问题描述

一个整数序列 A=(a1,a2,⋯,an)A=(a1​,a2​,⋯,an​) 的区间和为 Si,j=ai+ai+1+⋯+ajSi,j​=ai​+ai+1​+⋯+aj​ 。

给定整数序列 AA 和一个正整数 kk, 请问有多少个区间 [i,j][i,j] 满足 1≤i≤j≤n1≤i≤j≤n 且 Si,jSi,j​ 是 kk 非负整数倍。

输入格式

输入的第一行包含两个整数 n、kn、k, 用一个空格分隔。

第二行包含 nn 个整数 a1,a2,⋯,ana1​,a2​,⋯,an​, 相邻的整数之间用一个空格分隔。

输出格式

输出一行包含一个数表示满足条件的区间数量。

样例输入



样例输出



样例说明

满足条件的区间有 [1,2],[1,3],[1,6],[2,5],[3,3],[3,6],[4,6][1,2],[1,3],[1,6],[2,5],[3,3],[3,6],[4,6] 。

评测用例规模与约定

对于 4040 的评测用例, 1≤n≤500,1≤k≤101≤n≤500,1≤k≤10;

对于 6060 的评测用例, 1≤n≤20001≤n≤2000;

对于所有评测用例, 1≤n≤100000,1≤k≤109,−109≤ai≤1091≤n≤100000,1≤k≤109,−109≤ai​≤109 。

Java版

import java.util.*; /* 本题的核心 1、(sum[i]-sum[j])%k==0 || sum[i]%k==sum[j]%k 就代表满足条件 2、要求非负数。也就是->sum[i]>sum[j] */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 读取输入的 n 和 k int n = scanner.nextInt(); int k = scanner.nextInt(); // 用于存储余数和对应前缀和的映射 Map<Integer, List<Long>> umap = new HashMap<>(); // 初始化余数为 0 的情况，存入 -1 List<Long> initialList = new ArrayList<>(); initialList.add(-1L); umap.put(0, initialList); // 用于存储前缀和 long[] sum = new long[n]; int count = 0; for (int i = 0; i < n; i++) { // 读取当前输入的数 int cur = scanner.nextInt(); if (i == 0) { sum[i] = cur; } else { sum[i] = sum[i - 1] + cur; } // 计算当前前缀和对 k 取模的结果 long num = sum[i] % k; // 确保余数为非负 if (num < 0) { num += k; } // 获取对应余数的前缀和列表，如果不存在则创建一个新的列表 List<Long> vec = umap.computeIfAbsent((int) num, key -> new ArrayList<>()); // 使用二分查找找到第一个大于当前前缀和的位置 int index = upperBound(vec, sum[i]); // 累加符合条件的数量 count += index; // 将当前前缀和插入到合适的位置，保持列表有序 vec.add(index, sum[i]); } // 输出结果 System.out.println(count); } // 实现 upperBound 函数，用于找到第一个大于 target 的元素的索引 private static int upperBound(List<Long> list, long target) { int left = 0, right = list.size(); while (left < right) { int mid = left + (right - left) / 2; if (list.get(mid) <= target) { left = mid + 1; } else { right = mid; } } return left; } }

C++版

#include <iostream> #include <unordered_map> #include <vector> #include <algorithm> #define ll long long using namespace std; /* 本题的核心 1、(sum[i]-sum[j])%k==0 || sum[i]%k==sum[j]%k 就代表满足条件 2、要求非负数。也就是->sum[i]>=sum[j] */ int main(){ int n,k; cin>>n>>k; unordered_map<int,vector<ll>> umap; // 测试函数 // 初始化为1的情况 umap[0].push_back(-1); // 用-1，不影响其他 // 前缀和解法 ll sum[n]; int count = 0; int cur; for(int i=0; i<n; ++i){ cin>>cur; if(i==0) sum[i] = cur; else sum[i] = sum[i-1] + cur; ll num = sum[i]%k; if(num<0) num+=k; // 在处理前缀和的模运算时的一个常见操作 vector<ll>& vec = umap[num]; // 特喵的，迭代器，都不是一个 auto it = upper_bound(vec.begin(),vec.end(),sum[i]); // 当然，看看java版的，你自己也能手搓一个二分查找 count += it-vec.begin(); // 求出排在第几个 vec.insert(it,sum[i]); } cout<<count; return 0; } /* #include <iostream> #define ll long long using namespace std; // 前缀和，只能得到70分。终究还是要变异了！ int main() { ll n,k,flag=0; cin>>n>>k; ll arr[n]; ll sum[n]; for(int i=0; i<n; ++i){ cin>>arr[i]; if(i==0) sum[i]=arr[i]; else sum[i]=sum[i-1]+arr[i]; } // 天呐 for(int i=0; i<n; ++i){ for(int j=i; j<n; ++j){ ll s_num = 0; if(i==0) s_num=sum[j]; else s_num=sum[j]-sum[i-1]; if(s_num>=0&&s_num%k==0) flag++; } } cout<<flag; return 0; } */

知识点

做题期间遇到的困难。

1、multimap如何查询值 :: 基础学习 ::

本质上，这是一个非常简单的问题！但涉及基础，不知道，那就是不知道！

#include <iostream> #include <map> using namespace std; int main(){ // multimap导的是map的包 multimap<int,int> mmap; mmap.insert({1,2}); mmap.insert({1,3}); mmap.insert({2,4}); // 正确做法 auto it = mmap.find(1); while(it!=mmap.end()&&it->first==1){ cout<<it->first<<it->second<<endl; it++; } cout<<"---------------"<<endl; // 错误做法 for(auto itt=mmap.find(1); itt!=mmap.end(); ++itt){ // 这样的做法是错的，刹不住车 cout<<itt->first<<itt->second<<endl; } return 0; } --------------- 12 13 --------------- 12 13 24 ---------------

2、vector初始化-pair :: 基础拓展 ::

vector初始化的方式有很多，这里只是讲解特殊的那种 - 如何初始化pair<int,int>

 vector<pair<int,int>> res{ pair<int,int>(1,1) }; 

3、 <algorithm>库 upper_bound(二分查找的应用) :: 基础拓展 ::

• 查找，一个有序数列，并返回第一个大于某个数的位置！
• 可拓展性-cmp
• upper_bound内部是从前往后查询，且从小到大，若不是此顺序，可对cmp进行更改

#include "iostream" #include "vector" #include "algorithm" using namespace std; bool cmp(int a,int b){ return a>b; } int main(){ vector<int> res{1,23,4,6,1,234}; // 拓展之前 sort(res.begin(),res.end()); auto it = upper_bound(res.begin(),res.end(),7); // 初始值必须有序 auto i = it-res.begin(); cout<<i<<endl; // 拓展之后 sort(res.begin(),res.end(), cmp); auto it = upper_bound(res.begin(),res.end(),7, cmp); // 初始值必须有序 auto i = it-res.begin(); cout<<i<<endl; return 0; }

4、迭代器 :: 基础拓展 ::

好的，从资深算法工程师的角度，为你详细讲解 auto it = list.begin(); 中 it（迭代器）的相关知识和用法。

迭代器的基本概念：

迭代器(Iterator)，是一个非常抽象的概念，它提供了一种访问容器的方式。你可以把它看作一种特殊的指针，按照一定的顺序遍历容器（std::vector，std::list，std::map等）中的元素。并且能对其中的元素进行读取与修改。

迭代器的意义就是，就是让算法不直接依赖与具体的容器，增加复用性。

并且提供了一些基本的操作方法。如operate(++)移动到下一个元素，operate(*)获取该元素的值。

迭代器的常用操作：

• 解引操作（*）获取值
• 自增操作（++）移动到下一个位置
• 比较操作（!=、==）比较位置
• 其他操作（-- ...）某些特殊的操作，能够向前移动，it-list.begin -> 偏移量。

auto关键字

C++11中，引入了自动类型推导关键字，可以保证代码简洁，并且类型复杂时，用auto代替。

小结：

迭代器是 C++ 中非常重要的概念，它为容器和算法之间提供了统一的接口，使得算法能够灵活地应用于不同类型的容器上。在实际编程中，熟练掌握迭代器的用法对于编写高效、通用的代码至关重要。

5、二分查找 :: 基础巩固 ::

• 二分查找，本质是分治思想
• 基础 - 二分查找
• 变种 - 查找第一个
• 变种 - 查找最后一个
• 变种 - 查找第一个大于的数字 upper_bound(...);

基础二分查找

#include "iostream" using namespace std; int main(){ int arr[]{1,3,4,8,10}; // 二分查找 int l = 0, r = sizeof(arr)/ sizeof(int)-1; while(l<=r){ int mid = l+(r-l)/2; // 取中间 if(arr[mid]<1){ l = mid+1; }else if(arr[mid]>1){ // 小于 r = mid-1; }else{ cout<<mid<<endl; break; } } return 0; }

变种 - 查找第一个

#include "iostream" using namespace std; int main(){ int arr[]{0,1,1,3,4,8,10}; // 二分查找 int l = 0, r = sizeof(arr)/ sizeof(int)-1; int flag = 0; int result = 0; while(l<=r){ int mid = l+(r-l)/2; // 取中间 if(arr[mid]<flag){ l = mid+1; }else if(arr[mid]>flag){ // 小于 r = mid-1; }else{ result = mid; r = mid-1; } } cout<<result<<endl; return 0; }

变种 - 查找最后一个

#include "iostream" using namespace std; int main(){ int arr[]{0,1,1,3,4,8,10}; // 二分查找 int l = 0, r = sizeof(arr)/ sizeof(int)-1; int flag = 0; int result = 0; while(l<=r){ int mid = l+(r-l)/2; // 取中间 if(arr[mid]<flag){ l = mid+1; }else if(arr[mid]>flag){ // 小于 r = mid-1; }else{ result = mid; l = mid + 1; } } cout<<result<<endl; return 0; }

变种 - 查找第一个大于等于

#include "iostream" using namespace std; int main(){ int arr[]{0,1,1,3,4,8,10}; // 二分查找 int l = 0, r = sizeof(arr)/ sizeof(int)-1; int flag = 1; while(l<=r){ int mid = l+(r-l)/2; // 取中间 if(arr[mid]>=flag) r=mid-1; else { l = mid+1; } } cout<<l<<endl; return 0; }

6、超集  :: 知识拓展 ::

一个集合中的每一个元素都在另一个集合中，并且后者可能包含前者没有的元素。

例：TypeScript是JavaScript的超集。

7、map底层基本单位 :: 基础拓展 ::

std::map是键值对的集合，每个元素的类型是std::pair<const Key, T>，key是键的类型，T是值的类型。所以，用迭代器遍历std::map时，迭代器指向的元素是std::pair<const Key, T>;

借鉴博客：

1、数据结构 Hash表（哈希表）

2、简单易懂数据结构之哈希表

3、哈希表理论基础

4、数据结构 5分钟带你搞定哈希表(建议收藏)!!!

( •̀ ω •́ )✧点击这里，继续学习其他模块吧！