投稿
  1. 首页
  2. C

＜冲刺大厂之算法刷题＞Hash表

code • 2022-4-24 • C • 阅读 59

＜冲刺大厂之算法刷题＞Hash表,第1张

📒博客首页：热爱编程的大李子 📒

🌞文章目的：Hash表算法题整理分享🌞

🙏博主在学习阶段，如若发现问题，请告知，非常感谢🙏

💙同时也非常感谢各位小伙伴们的支持💙

🌈每日一语：承遇朝霞，年少正恰。整装戎马，刻印风华！ 🌈

💗感谢： 我只是站在巨人们的肩膀上整理本篇文章，感谢走在前路的大佬们！💗

🌟最后，祝大家每天进步亿点点！ 欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞！🌟

⭐️ ⭐️上篇文章-＜代码随想录二刷＞链表 ⭐️ ⭐️

文章目录
    • 242. 有效的字母异位词
        • 题目描述
        • 思路分析
        • 参考代码
    • 49. 字母异位词分组
        • 题目描述
        • 思路分析
        • 参考代码
    • 438. 找到字符串中所有字母异位词
        • 题目描述
        • 思路分析
        • 参考代码
    • 383. 赎金信
        • 题目描述
        • 思路分析
        • 参考代码
    • 349. 两个数组的交集
        • 题目描述
        • 思路分析
        • 参考代码
    • 350. 两个数组的交集 II
        • 题目分析
        • 思路分析
        • 参考代码
    • 202. 快乐数
        • 题目描述
        • 思路分析:
        • 参考代码
    • 1. 两数之和
        • 题目描述
        • 思路分析
        • 参考代码
    • 15. 三数之和
        • 题目描述
        • 思路分析
        • 参考代码
    • 18. 四数之和
        • 题目描述
        • 思路分析
        • 参考代码
    • 454. 四数相加 II
        • 题目描述
        • 思路分析
        • 参考代码
    • 总结

242. 有效的字母异位词 题目描述

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

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

示例 2:

输入: s = "rat", t = "car"
输出: false
思路分析

方法一:hash表

由于字符串中的都是小写字母,所以我们可以用数组来作为Hash表.

  • 将s中的字母出现的种类个数保存到数组arr中.

  • 将数组arr减掉t中字母出现的种类个数

  • 判断数组arr是否都为0,如果都为0,则说明 s和t是字母异位词.

方法二

直接sort排序,然后判断两个字符串是否相等.

参考代码 
#include
using namespace std;

//Hash表的使用 
bool isAnagram(string s, string t) {
	int arr[30] = {0};
	for(char ch : s){//统计s中的字母以及个数 
		arr[ch-'a']++;
	}
	for(char ch : t) {//用t中的字母和s中的进行抵消.. 
		arr[ch-'a']--;
	}
	for(int i = 0;i < 30;i++) {
		if(arr[i]!=0){
			return false;//s和t中有字符不一样. 
		}
	}
	return true; 
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

49. 字母异位词分组 题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]
思路分析

字母异位词其实就是两个串所使用的的字母以及个数都相同,只是顺序不同.所以如果两个串是字母异位词,则这两个串排序后是相等的.

  • 我们可以使用map来存储解决,因为不要求有序和可重复性,所以我们可以使用 unordered_map
  • 我们依次对字符串数组进行遍历,如果当前字符串排序后在map中出现过,则将其存入该key对应的val数组中.如果没有出现过则创建以该串为键的键值对.
  • 最终遍历Map将结果存放到vector数组中.
参考代码 
#include
using namespace std;

vector<vector<string>> groupAnagrams(vector<string>& strs) {
	unordered_map<string,vector<string>> M;
	vector<vector<string>> res;
	string s;
	for(int i = 0; i < strs.size(); i++) { //
		s = strs[i];
		sort(s.begin(),s.end());
		M[s].push_back(strs[i]);
	}
	//遍历输出
	for(unordered_map<string,vector<string>>::iterator it = M.begin(); it!=M.end(); it++) {
		res.push_back(it->second);
	}
	return res;
}
438. 找到字符串中所有字母异位词 题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]

解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]

解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。

思路分析

方法一:滑动窗口法+hash表

由于字符串中的都是小写字母,所以我们可以用数组的下标进行映射.即选择数组类型的hash表; 由于求的是子串的异位词,可以使用一个滑动窗口法:窗口大小固定,从前往后移动,寻找符合的子串.

  • 初始化滑动窗口.也就是对arrS和arrP初始化. arrS中至少含有arrP中的所有元素.
  • 判断初始化后的窗口是否相等,如果相同则将其实下标0加入结果集.
  • S滑动窗口向后移动寻找满足的子串满足是P的异位词,并将满足的起始下标加入结果集.
  • 返回结果集
参考代码 
bool judgeArr(int arr1[],int arr2[]) { //判断两个数组是否相等
	for(int i = 0; i < 30; i++) {
		if(arr1[i]!=arr2[i]) {
			return false;
		}
	}
	return true;
}
//滑动窗口法+hash表
vector<int> findAnagrams(string s, string p) {
	int m = s.size();
	int n = p.size();
	vector<int> res;

	int arrS[30] = {0};
	int arrP[30] = {0};

	if(s.size() <p.size()) {//长度s  < p,则s中不可能存在子串 和p是异位词
		return {};
	}

	//初始化滑动窗口 s的窗口至少含有p中的所有元素
	for(int i = 0; i < n; i++) {
		arrS[s[i]-'a']++;
		arrP[p[i]-'a']++;
	}
	if(judgeArr(arrS,arrP)) {//判断初始化后的窗口是否相等
		res.push_back(0);
	}
	//s滑动窗口移动寻找子串满足是p的异位词   注意:s的窗口大小和p相等
	for(int i = n; i<m; i++) {
		arrS[s[i]-'a']++;
		arrS[s[i-n]-'a']--;
		if(judgeArr(arrS,arrP)) {
			res.push_back(i-n+1);
		}
	}
	return res;
}
383. 赎金信 题目描述

为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。

给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符构成。

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true
思路分析

方法一:hash表

因为是字符,所以可以采用数组的hash表(也可以使用unordered_map的hash表,因为考虑到效率而且还不需要排序)
**注:**使用数组还是使用set/map类型的hash表,要认真考虑.如果元素用数组可以很好的表示并且范围很小,那就考虑数组.比如元素字符… 本题使用数组较为简单

方法二:双指针

  1. 先对两个串排序.
  2. i指向ransomNote串,j指向magazine串.然后从前往后遍历俩串,如果相同就都++,如果j对应的字符大于了i对应的字符,说明不满足了. 如果j对应的字符小于i对应的字符,说明magazine中的该字符是满足的而且还多余.
  3. 如果i能遍历完ransomNote,则说明能找到符合题意的串.
参考代码

方法一:hash表(数组)

//直接LeetCode242进行改造...  数组做hash表
bool canConstruct(string s, string t) {
	int arr[30] = {0};
	for(char ch : s){//统计s中的字母以及个数 
		arr[ch-'a']++;
	}
	for(char ch : t) {//用t中的字母和s中的进行抵消.. 
		arr[ch-'a']--;
	}
	for(int i = 0;i < 30;i++) {
		if(arr[i]>0){
			return false;//s和t中有字符不一样. 
		}
	}
	return true; 
}

//使用map作为哈希表
bool canConstruct(string s1, string s2) {
	if(s1.size()>s2.size()) {
		return false;
	}
	unordered_map<char,int> sMap;
	for(char c : s2) {
		if(sMap.find(c)==sMap.end()) {
			sMap[c] = 1;
		} else {
			sMap[c]++;
		}
	}
	for(char c : s1) {
		if(sMap.find(c)!=sMap.end()) {
			sMap[c]--;
			if(sMap[c]<0){
				return false;
			}
		}else{
			return false;
		}
	}
	return true;
}

  • 时间复杂度 O(n)

  • 空间复杂度O(n)

方法二:双指针

bool canConstruct(string ransomNote, string magazine) {
	if(ransomNote.size()>magazine.size()) {
		return false;
	}
	sort(ransomNote.begin(),ransomNote.end());
	sort(magazine.begin(),magazine.end());
	//cout<
	int i,j;
	for(i = 0,j = 0; i < ransomNote.size(); i++,j++) {
		if(j>=magazine.size()) {
			return false;
		}
		if(ransomNote[i]==magazine[j]) {
			continue;
		} else if(ransomNote[i]>magazine[j]) {
			i--;
		} else {
			return false;
		}
	}
	return true;
}
349. 两个数组的交集 题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
思路分析

方法一:hash表

  • 由样例可知,最后的结果是要去重的. 我们选择unordered_set类型的hash表:输出结果中的每个元素一定是唯一的， 同时可以不考虑输出结果的顺序

**注:**由于数组中数的返回比较大,所以不建议使用数组来作为hash表.

方法二:暴力法(此法代码省略)

  • 先给nums1和nums2排序.

  • 然后双层循环判断nums1的元素是否出现在了nums2中.

  • 判断过程中要进行去重:nums1中循环的元素和前一个相等则不处理,不相等再去nums2中判断是否存在

  • 将nums1和nums2都存在的元素加入结果集

参考代码

方法一:hash表

#include
using namespace std;

//方法一: 先给nums1和nums2排序.然后双层循环判断nums1的元素是否出现在了nums2中.遍历时,如果元素和前一个相等则不处理,不相等再去nums2中判断是否存在.
//方法二:先去重使用nums1_set 然后遍历nums2,判断元素在nums1_set中是否出现,如果出现则加入结果集合..O(N)   unordered_set的查找效率是O(1)
//另外通过这个题,也要学到vector初始化set,set初始化vector的知识点
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
	unordered_set<int> result_set;//结果集
	unordered_set<int> nums1_set(nums1.begin(),nums1.end()) ;
	for(int i = 0; i < nums2.size(); i++) {
		//如果发现 nums2的元素 ,在nums1_set中出现过
		if(nums1_set.find(nums2[i])!=nums1_set.end()) {
			result_set.insert(nums2[i]) ;
		}
	}
	return vector<int>(result_set.begin(),result_set.end());
}
350. 两个数组的交集 II 题目分析

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

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

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
思路分析

方法一:hash表

因为不去重,不考虑顺序,而且考虑到了效率我们可以采用unordered_map类型的hash表

  • 把nums1中的元素放到unordered_map nums1_map中,然后遍历nums2中的每个元素num.
  • 如果num在numsMap的值>0,则说明可以放到交集里面…如果等于0,则从numsMap中移除.

方法二:双指针

思路与LeetCode384相似,不再赘述

参考代码

方法一:hash表

//方法一:使用unordered_map解决.  原因:因为同一个数存在多个,可以使用键值对来进行存储,结果不要求顺序.
//时间复杂度O(N)  空间复杂度O(N)
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
	vector<int> result;
	unordered_map<int,int> nums1_map;
	for(int i = 0; i < nums1.size(); i++) { //初始化nums1_map
		nums1_map[nums1[i]]++;
	}
	//遍历nums2,将重复的元素加入结果集.
	for(int i = 0; i < nums2.size(); i++) {
		if(nums1_map.find(nums2[i])!=nums1_map.end()) {
			nums1_map[nums2[i]]--;
			result.push_back(nums2[i]);//元素放入结果集
			if(nums1_map[nums2[i]]==0) { //如果已经减到了0,则移除
				nums1_map.erase(nums2[i]);
			}
		}
	}
	return result;
}
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

方法二:双指针

//方法二: 双指针
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
	int i = 0,j = 0;
	vector<int> result;
	//排序 
	sort(nums1.begin(),nums1.end());
	sort(nums2.begin(),nums2.end());
	while(i<nums1.size()&&j<nums2.size()){
		if(nums1[i]==nums2[j]){//如果想等 
			result.push_back(nums1[i]);//加入结果集 
			i++;//同时移动 
			j++;
		}else if(nums1[i]<nums2[j]){//值小的指针往前移动 
			i++;
		}else if(nums1[i]>nums2[j]){
			j++;
		}
	}
	return result;
}
202. 快乐数 题目描述

编写一个算法来判断一个数 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
思路分析:

注意: 题目中的可能会无限循环,也就是说在求和的过程中,sum会重复出现.

  • 所以我们就可以对该数进行快乐的判断,每次如果不是1,说明该数目前不是快乐数.
  • 同时要在set中寻找该数是否曾经出现过,如果出现过则说明出现了循环则一定不是快乐数.
  • 如果还没有出现则持续进行判断…
参考代码 
#include
using namespace std;

int getSum(int x){//将数替换成数字的平方和 
	int sum = 0;
	while(x){
		sum+=(x%10)*(x%10);
		x /= 10;
	}
	return sum;
}
//由于只需要存这个元素在集合中是否存在,而且不需要重复,所以我们使用unordered_set 
unordered_set<int> set;

bool isHappy(int n) {
	int res = getSum(n);
	
	while(res!=1){
		if(set.find(res)!=set.end()){
			return false;
		}else{
			set.insert(res);
		}
		res = getSum(res);
	}
	return true;
}
1. 两数之和 题目描述

给定一个整数数组 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]
思路分析

方法一:暴力法

双层for循环走起来 ~ ~ ~

方法二:hash表(unordered_map)

  • 因为每次不仅要存数,还要存储其下标,所以我们使用map,因为不需要有序和重复性,我们可以选择:unordered_map M

  • 用i遍历所有的元素,在M中查找是否存在元素 target - nums[i],如果存在则说明找到了,返回当前元素和这个元素的下标.

  • 如果没有找到则将当前元素和下标插入到M中.

参考代码

方法一:暴力法

//方法一:暴力法 
vector<int> twoSum(vector<int>& nums, int target) {
	for(int i = 0;i < nums.size();i++) {
		for(int j = i+1;j < nums.size();j++){
			return {i,j};
		}
	}
	return {};
}
  • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度: O ( 1 ) O(1) O(1)

方法二:hash表

vector<int> twoSum(vector<int>& nums, int target) {
	unordered_map<int,int> M;//存放元素以及对应的下标
	for(int i = 0; i < nums.size(); i++) {
		unordered_map<int,int>::iterator iter = M.find(target-nums[i]);//查找其和为target的另外 一个元素是否存在
		if(iter!=M.end()) {
			return {i,iter->second};
		}
		M.insert(pair<int,int>(nums[i],i));//如果没有,则将当前元素插进来.
	}
	return {};//写这个只是为了编译通过,实际运行根本不会走这一步..
}
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
15. 三数之和 题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]
思路分析

排序 + 双指针

(1). 特判，对于数组长度 n，如果数组长度小于 3，返回 []。
(2). 对数组进行排序。
(3).遍历排序后数组：

  • 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。

  • 对nums[i] (代表的就是a)进行去重.

  • 令左指针 L=i+1，右指针 R=n-1，当 L

(4) 当 nums[i]+nums[L]+nums[R]==0执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
(5).若和大于 0，说明nums[R] 太大，R左移
(6).若和小于 0，说明 nums[L] 太小，L右移

复杂度分析

  • 时间复杂度： O ( n 2 ) O(n^2) O(n2)
    数组排序 O(n logn)，遍历数组O(n)，双指针遍历 O(n)，总体 O(n logn)+O(n)∗O(n)，
  • 空间复杂度： O ( 1 ) O(1) O(1)
参考代码 
#include
using namespace std;


vector<vector<int>> threeSum(vector<int>& nums) {
	int L,R,sum;
	vector<vector<int>> res;
	if(nums.size()<3) {
		return {} ;
	}
	//进行排序
	sort(nums.begin(),nums.end()) ;
	//如果第一个元素就>0,那么后面的元素一定 > 0
	if(nums[0]>0) {
		return {};
	}

	//遍历元素+双指针
	for(int i = 0; i<nums.size(); i++) {
		if(nums[i]>0) {
			return res;
		}
		if(i>0&&nums[i]==nums[i-1]) { //进行去重
			continue;
		}
		L = i+1;
		R = nums.size()-1;
		while(L < R) {//采用双指针法 枚举所有的三元对情况 
			sum = nums[i]+nums[L]+nums[R];
			if(!sum) {
				res.push_back({nums[i],nums[L],nums[R]});
				//进行去重
				while(L + 1<R && nums[L]==nums[L+1]) {
					L++;
				}
				while(R-1 > L && nums[R]==nums[R-1]) {
					R--;
				}
				L++;
				R--;
			} else if(sum > 0) {
				R--;
			} else if(sum < 0) {
				L++;
			}
		}

	}
	return res;
}
18. 四数之和 题目描述

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

0 <= a, b, c, d < n
a、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]]
思路分析

和三数之和解决思路基本一致.三数之和只是 i 固定,左右指针进行变化.
四数之和是i,j固定,然后左右指针进行变化,当左右指针变化一轮后,j进行后移一位.j移动完一轮后,i后移一位…

参考代码 
#include
using namespace std;
//这个题思路和上一个题非常相似
vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int>> res;
	int len = nums.size();
	long long i,j,k,l, sum;
	if(nums.size()<4) {
		return {};
	}
	//进行排序
	sort(nums.begin(),nums.end()) ;
	// if(nums[0]>target){//这里不能根据第一个数来判断最终结果,因为target可能是正数,负数,0
	//     return {};
	// }

	//定义两个变量+双指针 枚举所有的情况
	for(i = 0; i <= len-4; i++) {
		//去重i元素
		if(i > 0 && nums[i]==nums[i-1]) {//去重
			continue;
		}
		for( j = i+1; j <= len - 3; j++) {
			//去重
			if(j > i+1 && nums[j] == nums[j-1]) {
				continue;
			}
			//定义双指针
			int k = j+1;
			int l = len  - 1;
			while(k < l) {
				sum = 0;
				sum += nums[i];
				sum += nums[j];
				sum += nums[k];
				sum += nums[l];
				if(sum==target) {
					res.push_back({nums[i],nums[j],nums[k],nums[l]});
					//进行去重
					while(k+1 < l &&nums[k] == nums[k+1] ) {
						k++;
					}
					while(l-1>k&& nums[l]==nums[l-1]) {
						l--;
					}
					//指针移动
					k++;
					l--;
				} else if(sum < target) {
					k++;
				} else if(sum > target) {
					l--;
				}
			}
		}
	}
	return res;
}
454. 四数相加 II 题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2

解释：
两个元组如下：

  1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
思路分析

由于a,b,c,d是在四个数组里面的,所以可以使用四个循环. 为了降低时间复杂度,我们可以将a、b分为一组,c、d分为一组. 利用map类型的hash表统计其出现的次数.

  • 首先定义 一个unordered_map ，key放a和b两数之和，value 放a和b两数之和出现的次数。
  • 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
  • 在遍历大C和大D数组，如果 0-(c+d) 在map中出现过的话，统计其出现的次数.
  • 最后返回统计值 cnt
参考代码 
#include
using namespace std;

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
	unordered_map<int,int> M;
	int cnt = 0;
	for(int A : nums1){
		for(int B : nums2){
			M[A+B]++;
		}
	}
	for(int C: nums3){
		for(int D: nums4){
			auto iter = M.find(0-A-B);
			if(M.find(0-A-B)!=M.end()) {
				cnt+=iter->second;
			}
		}
	}
	return cnt;
}
总结

OK，今天关于hash表算法整理就到这里的，希望本篇文章能够帮助到大家，同时也希望大家看后能学有所获！！！

好了，我们下期见~

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/713782.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-24
下一篇 2022-04-24

发表评论

登录后才能评论

评论列表（0条）

保存