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

建议：本题是?使用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;
}

暂时不懂

——未完待续