代码随想录算法训练营day7|454.四数相加II 、383.赎金信、15.三数之和、18.四数之和

发布时间:2024年01月14日
?454.四数相加II?

建议:本题是?使用map?巧妙解决的问题,好好体会一下?哈希法?如何提高程序执行效率,降低时间复杂度,当然使用哈希法?会提高空间复杂度,但一般来说我们都是舍空间?换时间,?工业开发也是这样。

题目链接/文章讲解/视频讲解:代码随想录

?383.?赎金信??

建议:本题?和?242.有效的字母异位词?是一个思路?,算是拓展题?

题目链接/文章讲解:代码随想录

?15.?三数之和?

建议:本题虽然和?两数之和?很像,也能用哈希法,但用哈希法会很麻烦,双指针法才是正解,可以先看视频理解一下?双指针法的思路,文章中讲解的,没问题?哈希法很麻烦。?

题目链接/文章讲解/视频讲解:代码随想录

?18.?四数之和??

建议:?要比较一下,本题和?454.四数相加II?的区别,为什么?454.四数相加II?会简单很多,这个想明白了,对本题理解就深刻了。?本题?思路整体和?三数之和一样的,都是双指针,但写的时候?有很多小细节,需要注意,建议先看视频。?

题目链接/文章讲解/视频讲解:代码随想录


vector<int>twoSum(vector<int>& nums, int target) {
	unordered_map<int, int> map;
	for (int i = 0; i < nums.size(); i++) {
		auto iter = map.find(target - nums[i]);
		if (iter != map.end()) {
			return{ iter->second,i };
		}
		map.insert(pair<int, int>(nums[i], i));
	}
	return {};
}

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
	unordered_map<int, int> umap;
	for (int a : A) {
		for (int b : B) {
			umap[a + b]++;
		}
	}
	int count = 0;
	for (int c : C) {
		for (int d : D) {
			if (umap.find(0 - (c + d)) != umap.end()) {
				count += umap[0 - (c + d)];
			}
		}
	}
	return count;
}

bool canConstruct(string ransomNote, string magazine) {
	int record[26] = { 0 };
	if (ransomNote.size() > magazine.size()) {
		return false;
	}
	for (int i = 0; i < magazine.size(); i++) {
		record[magazine[i] - 'a']++;
	}
	for (int j = 0; j < ransomNote.length(); j++) {
		record[ransomNote[j] - 'a']--;
		if (record[ransomNote[j] - 'a'] < 0) {
			return false;
		}
	}
	return true;
}

暂时不懂

——未完待续

文章来源:https://blog.csdn.net/2302_79277225/article/details/135407152
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。