题目链接：454 四数相加 II
题干：给定四个包含整数的数组列表?A , B , C , D ,计算有多少个元组 (i, j, k, l)?，使得?A[i] + B[j] + C[k] + D[l] = 0。
思考：哈希解法。把四数相加问题转换为两数相加问题，让两个数组元素相加的所有可能的值的值和值出现的次数以键值对存入容器map中。再把另两个数组相加的所有值对应的相反数在容器map中查找，若存在则结果result加该键值对的值出现次数。
代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> map;//记录a+b结果的值和出现次数
int result = 0;
//将a+b的所有可能都存入容器
for (int a : nums1) {
for (int b : nums2)
map[a+b]++;//相同的结果次数加一
}
//c+d的值在容器里做匹配
for (int c : nums3) {
for (int d : nums4) {
auto it = map.find(- (c + d));
if (it != map.end())
result += it->second;
}
}
return result;
}
};题目链接：383 赎金信
题干：给你两个字符串：ransomNote?和?magazine?，判断?ransomNote?能不能由?magazine?里面的字符构成。如果可以，返回?true?；否则返回?false?。
magazine?中的每个字符只能在?ransomNote?中使用一次。1 <= ransomNote.length, magazine.length <= 105ransomNote?和?magazine?由小写英文字母组成思考：哈希解法。将magazine中的字符以及其出现的次数以键值对的形式存入容器map中。再遍历ransomNote的每个字符，如果字符存在容器map中，将其对应的次数值减一，处理后判断此数值是否为0，如果是则删除该键值对。循环过程中一旦查询不到的字符就返回false。
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char,int> map;
for (char s : magazine) //将字符串magazine里面的字符和出现次数存入容器中
map[s]++;
for (char s : ransomNote){
auto it = map.find(s);
if (it == map.end()) //没找到对应的字符或字符出现的次数不够
return false;
it->second--;
if (it->second == 0) //字符出现次数用完时删除
map.erase(s);
}
return true;
}
};题目链接：15 三数之和
题干：给你一个整数数组?nums?，判断是否存在三元组?[nums[i], nums[j], nums[k]]?满足?i != j、i != k?且?j != k?，同时还满足?nums[i] + nums[j] + nums[k] == 0?。请你返回所有和为?0?且不重复的三元组。
3 <= nums.length <= 3000-105 <= nums[i] <= 105思考一：双指针法
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
std::sort(nums.begin(),nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) //排序后首个元素值大于0则不可能凑出三元组
return result;
if (i > 0 && nums[i] == nums[i - 1]) //除首个元素以外相同的元素只处理首个
continue;
int left = i + 1; //左指针
int right = nums.size() - 1; //右指针
while (left < right) {
if (nums[i] + nums[left] + nums[right] > 0) //值大则右指针移到较小值
right--;
else if (nums[i] + nums[left] + nums[right] < 0) //值小则左指针移到较大值
left++;
else {
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
while (right > left && nums[left] == nums[left + 1]) //寻找第一个不同值的右指针
left++;
while (right > left && nums[right] == nums[right - 1]) //寻找第一个不同值的左指针
right--;
left++;
right--;
}
}
}
return result;
}
};思考二：哈希解法。两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过。把符合条件的三元组放进vector中，然后再去重（超时，去重处理复杂）
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[0] > 0)
return result;
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 target = - (nums[i] + nums[j]);
if(set.find(target) != set.end()) {
result.push_back({nums[i],nums[j],target});
set.erase(target); //三元组c去重
} else {
set.insert(nums[j]);
}
}
}
return result;
}
};题目链接：18 四数之和
题干：给定一个包含?n 个整数的数组?nums?和一个目标值?target，判断?nums?中是否存在四个元素 a，b，c?和 d?，使得?a + b + c + d?的值与?target?相等？找出所有满足条件且不重复的四元组。
1 <= nums.length <= 200思考：类似三数之和问题，双层循环尝试四元组的前两个值，再用双指针尝试后面两个值。较三数之和问题，这题的剪枝和去重有两次且剪枝只处理正数的情况。
代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] >= 0 && nums[i] > target) //首次剪枝
break;
if (i > 0 && nums[i] == nums[i - 1]) //首次去重
continue;
for (int j = i + 1; j < nums.size(); j++){
if (nums[i] + nums[j] >= 0 && nums[i] + nums[j] > target) //二次剪枝
break;
if (j > i + 1 && nums[j] == nums[j - 1]) //二次去重
continue;
int left = j + 1;
int right = nums.size() - 1;
while (left < right) {
if ((long) nums[i] + nums[j] + nums[left] + nums[right] > target)
right--;
else if ((long) nums[i] + nums[j] + nums[left] + nums[right] < target)
left++;
else {
result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
while (left < right && nums[left] == nums[left + 1])
left++;
while (left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
}
}
}
}
return result;
}
};哈希表专题总结：