# 四数相加 II

题目链接🔗

本题是四个独立的数组，不用考虑四个重复的元素相加等于 0 的情况。

本题解题步骤：

	class Solution {
	public:
	int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
	unordered_map<int, int> umap;
	// 遍历 A 和 B，求 a+b 出现的次数
	for(int a : nums1)
	for(int b : nums2)
	umap[a+b]++;
	int count = 0;
	// 遍历 C 和 D，求 0-(c+d) 是否在 map 中出现过，出现过统计次数
	for(int c : nums3) {
	for(int d : nums4) {
	if(umap.find(0-(c+d)) != map.end()){
	count += umap[0-(c+d)]
	}
	}
	}
	return count;
	}
	};

# 赎金信

题目链接🔗

题目假设两个字符串只含小写字母，因此可以使用数组来当哈希表使用。

本题求 reasomNote 字符串能不能由 magazine 字符串构成，因此先统计 magazine 字符串中各字符数量。

	class Solution {
	public:
	bool canConstruct(string ransomNote, string magazine) {
	int a[26] = {0};
	for(char c : magazine)
	a[c - 'a']++;

	for(char c : ransomNote)
	a[c - 'a']--;

	for(int i = 0; i < 26; i++) {
	if(a[i] < 0)
	return false;
	}
	return true;
	}
	};

题目链接🔗

本题不能包含重复的三元组，需要去重。

哈希表解法的去重过程比双指针法要复杂适合使用双指针法，双指针法之后会着重解释。

双指针法要考虑

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	vector<vector<int>> result;
	sort(nums.begin(), nums.end());
	// 找出 a + b + c = 0
	// a = nums[i], b = nums[j], c = -(a + b)
	for (int i = 0; i < nums.size(); i++) {
	// 排序之后如果第一个元素已经大于零，那么不可能凑成三元组
	if (nums[i] > 0) {
	break;
	}
	if (i > 0 && nums[i] == nums[i - 1]) { // 三元组元素 a 去重
	continue;
	}
	unordered_set<int> set;
	for (int j = i + 1; j < nums.size(); j++) {
	if (j > i + 2
	&& nums[j] == nums[j-1]
	&& nums[j-1] == nums[j-2]) { // 三元组元素 b 去重
	continue;
	}
	int c = 0 - (nums[i] + nums[j]);
	if (set.find(c) != set.end()) {
	result.push_back({nums[i], nums[j], c});
	set.erase(c);// 三元组元素 c 去重
	} else {
	set.insert(nums[j]);
	}
	}
	}
	return result;
	}
	};

题目链接🔗

和三数之和一样，着重在双指针法时再讲解。

如果使用哈希表，可以将枚举前三个数，哈希后一个数的时间复杂度 $O(n^3)$ 降低为，枚举前两个数，哈希后两个数的 $O(n^2)$ 。降低枚举的复杂度，提升构建 hash 的复杂度。使整体复杂度降为 $O(n^2)$ 。