代码随想录算法训练营第七天 | 454.四数相加II 、 383. 赎金信 、 15. 三数之和 、18. 四数之和
454.四数相加II
题目链接：https://leetcode.cn/problems/4sum-ii/description/
文章讲解：代码随想录
视频讲解：学透哈希表，map使用有技巧！LeetCode：454.四数相加II
本题可使用哈希法，四个独立的数组只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，即不需要考虑去重的操作。所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！
思路：两两分组，算出第一个数组和第二个数组的和A+B，然后在第三和第四个数组和C+D中找是否有满足条件的。
由于数组元素可能很大，用数组下表做映射（即数值是几对应第几个元素+1）显然是不够的，因此考虑用set或map。
因为不仅要统计A+B是否出现过，还要统计A+B出现次数，所以用map。
本题解题步骤：
1、首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2、遍历大A和大B数组，统计两个数组元素之和，以及和出现的次数，放到map中。
3、定义int变量count，用来统计 a+b+c+d = 0出现的次数。
4、再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5、最后返回统计值 count 就可以了
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap; //key:a+b的数值，value:a+b数值出现的次数
// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
for (int a : A) { //每次循环中，a依次获取容器A中的一个元素值！！
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // 统计a+b+c+d = 0 出现的次数
// 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
【注】
1、umap[a + b]++：
umap的key是a + b，value是a+b出现的次数，即umap[a + b]是次数，因此后面count要+umap[0-(c+d)]
2、与上一天最后一题统一，这个也可以先定义一个迭代器：it=umap.find(0-(c+d))，则it->first是key，it->second是value。
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> umap;
for(int a:nums1){
for(int b:nums2){
umap[a+b]++;
}
}
int count = 0;
for(int c:nums3){
for(int d:nums4){
auto it=umap.find(0-(c+d));
if(it != umap.end()){
count += it->second;
}
}
}
return count;
}
};
383. 赎金信
题目链接：https://leetcode.cn/problems/ransom-note/description/
文章讲解：代码随想录
暴力解法
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for (int i = 0; i < magazine.length(); i++) {
for (int j = 0; j < ransomNote.length(); j++) {
// 在ransomNote中找到和magazine相同的字符
if (magazine[i] == ransomNote[j]) {
ransomNote.erase(ransomNote.begin() + j); // ransomNote删除这个字符
break;
}
}
}
// 如果ransomNote为空，则说明magazine的字符可以组成ransomNote
if (ransomNote.length() == 0) {
return true;
}
return false;
}
};
【注】
1、erase 是 C++ 标准库中容器类的成员函数，用于删除容器中的一个或多个元素
2、ransomNote.begin() + j：begin()返回指向字符串开头的迭代器，+ j即迭代器向前移动 j 个位置
整体含义：删除字符串中第 j 个字符
3、length()函数通常用于获取字符串（std::string）的长度（即字符的个数）
哈希解法
因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。依然是数组在哈希法中的应用。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26] = {0};
//add
if (ransomNote.size() > magazine.size()) {
return false;
}
for (int i = 0; i < magazine.length(); i++) {
// 通过record数据记录 magazine里各个字符出现次数
record[magazine[i]-'a'] ++;
}
for (int j = 0; j < ransomNote.length(); j++) {
// 遍历ransomNote，在record里对应的字符个数做--操作
record[ransomNote[j]-'a']--;
// 如果小于零说明ransomNote里出现的字符，magazine没有
if(record[ransomNote[j]-'a'] < 0) {
return false;
}
}
return true;
}
};
【注】
1、因为是判断ransomNote能不能由magazine里面的字符构成，所以先记录 magazine里各个字符出现次数。
15. 三数之和
题目链接：https://leetcode.cn/problems/3sum/description/
文章讲解：代码随想录
视频讲解：梦破碎的地方！| LeetCode：15.三数之和
哈希解法
与454即第一题不同，本题要涉及去重（因为是同一个数组）。
两层for循环就可以确定两个数值，可以使用哈希法来确定 第三个数 0-(a+b) 或者 0 - (a + c) 是否在数组里出现过，这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时。
这道题目使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码。
class Solution {
public:
// 在一个数组中找到3个数形成的三元组，它们的和为0，不能重复使用（三数下标互不相同），且三元组不能重复。
// b（存储）== 0-(a+c)（检索）
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
// 如果a是正数，a
if (nums[i] > 0)
break;
// [a, a, ...] 如果本轮a和上轮a相同，那么找到的b，c也是相同的，所以去重a
if (i > 0 && nums[i] == nums[i - 1])
continue;
// 这个set的作用是存储b
unordered_set<int> set;
for (int k = i + 1; k < nums.size(); k++) {
// 去重b=c时的b和c
if (k > i + 2 && nums[k] == nums[k - 1] && nums[k - 1] == nums[k - 2])
continue;
// a+b+c=0 <=> b=0-(a+c)
int target = 0 - (nums[i] + nums[k]);
if (set.find(target) != set.end()) {
result.push_back({nums[i], target, nums[k]}); // nums[k]成为c
set.erase(target);
}
else {
set.insert(nums[k]); // nums[k]成为b
}
}
}
return result;
}
};
双指针法
拿这个nums数组来举例，首先可以将数组排序（因为题目只要返回元素值，不要求返回索引，使用双指针关键要先排序），然后有一层for循环，i从下标0的地方开始，同时定义一个下标 left 定义在i+1的位置上，定义下标 right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得 a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
接下来如何移动left和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
双指针思路比较简单，但去重是关键!! 说到去重，其实主要考虑三个数的去重。a, b ,c, 对应的就是nums[i]，nums[left]，nums[right]。
1、a的去重
a如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。但这里有一个问题，是判断nums[i]与 nums[i + 1]是否相同，还是判断nums[i]与nums[i-1] 是否相同。
如果判断nums[i]与 nums[i + 1]是否相同，那我们就把三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断下一个也是-1，那这组数据就pass了。我们要做的是不能有重复的三元组，但三元组内的元素是可以重复的！所以应该判断nums[i]与nums[i-1] 是否相同：
if (i > 0 && nums[i] == nums[i - 1]) { //要i>0防止出现负数
continue;
}
这么写就是每次我们判断 nums[i] 前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到结果集里。这是一个非常细节的思考过程。
为什么看前一位就行了？
因为有排序保证，相同的元素相邻，所以只需比较前一位。
2、b和c的去重
当left右移和right左移后，判断移动后的元素与之前元素是否相等，若相等，则继续移动。
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[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) { //剪枝操作
return result; //也可以直接break跳出for循环，执行最下面的return，效果一样
}
// 错误去重a方法，将会漏掉-1,-1,2 这种情况
/*
if (nums[i] == nums[i + 1]) {
continue; //跳过当前元素，直接处理下一个
}
*/
// 正确去重a方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组，因此应该放在后面，确保先有第一组数据！！
/*
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
*/
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]});
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};
无注释版本：
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[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
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[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
};
【注】
1、sort是对nums进行排序
2、push_back向容器末尾添加新元素
3、result.push_back(vector{nums[i],nums[left],nums[right]}); 为何用{ }？
使用大括号{ }是列表初始化的方式
// 方法1：使用大括号列表初始化（简洁）
result.push_back(vector{nums[i], nums[left], nums[right]});
// 方法2：传统写法（更繁琐）
vector temp;
temp.push_back(nums[i]);
temp.push_back(nums[left]);
temp.push_back(nums[right]);
result.push_back(temp);
4、为何if (nums[i] + nums[left] + nums[right] > 0) right–; 用if
而while (right > left && nums[right] == nums[right - 1]) right–; 用while?
用 if 是因为每次循环只需要根据当前和移动一次指针（除非找到和为0的情况，则多做一些操作）。
用 while 是为了跳过所有重复的连续元素，确保不会记录重复的三元组。
18. 四数之和
题目链接：https://leetcode.cn/problems/4sum/description/
文章讲解：代码随想录
视频讲解：难在去重和剪枝！| LeetCode：18. 四数之和
四数之和与15.三数之和是一个思路，都是使用双指针法, 基本解法就是在15.三数之和的基础上再套一层for循环。还要注意一些细节，主要是剪枝和去重的部分。
去重指的是避免重复结果的过程，主要解决"同一问题有多个解，但最终结果相同"的情况。
剪枝属于算法优化，指的是通过判断，提前终止不可能得到有效解的分支，减少搜索空间，提高算法效率。
例如： 不可以判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0就返回了，因为 0 不是负数，四数之和这道题目target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[k] > target && (nums[k] >=0 || target >= 0)就可以了。
15.三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和时间复杂度是 O ( n 2 ) O(n^2) O(n2)，四数之和时间复杂度是 O ( n 3 ) O(n^3) O(n3)。
那么一样的道理，五数之和、六数之和等等都采用这种解法。
对于15.三数之和的双指针法就是将原本暴力 O ( n 3 ) O(n^3) O(n3)的解法，降为 O ( n 2 ) O(n^2) O(n2)的解法，四数之和的双指针解法就是将原本暴力 O ( n 4 ) O(n^4) O(n4)的解法，降为 O ( n 3 ) O(n^3) O(n3)的解法。
解题思路：
分为k,i,left,right四个指针，先处理k（剪枝+去重），然后处理i（（剪枝+去重）,剪枝思路与处理k相同，只是把nums[k]换成nums[k] + nums[i]），然后是left和right（去重）
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
// 剪枝处理
if (nums[k] > target && nums[k] >= 0) {
break; // 这里使用break，直接跳出整个for循环，统一通过最后的return返回9
}
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue; // 跳过本次循环，执行 k++
}
for (int i = k + 1; i < nums.size(); i++) {
// 2级剪枝处理
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// 对nums[i]去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
【注】
1、break
立即终止当前循环，直接跳出循环体，继续执行循环后面的代码。
continue
跳过本次循环的剩余部分，直接进入下一次循环迭代。
2、在四数之和问题中，使用 (long) 进行类型转换是为了防止整数溢出。
一定要有long，否则会出错！！
3、result.push_back的时候别忘了vector类型定义
双指针总结
我们来回顾一下，几道题目使用了双指针法。
双指针法将时间复杂度：
O
(
n
2
)
O(n^2)
O(n2)的解法优化为
O
(
n
)
O(n)
O(n)的解法。也就是降一个数量级，题目如下：
27.移除元素
15.三数之和
18.四数之和
链表相关双指针题目：
206.反转链表
19.删除链表的倒数第N个节点
面试题 02.07. 链表相交
142题.环形链表II
双指针法在字符串题目中还有很多应用，后面还会介绍到。
总结
哈希表的map中的key和value的概念要弄清，key用来查找有没有重复出现，value一般用来记录次数。
当涉及统计字母的题目时，可以先考虑用数组的哈希解法。
要掌握剪枝与去重的逻辑。
哈希表总结
文章讲解：代码随想录
三种哈希结构：
数组
set（集合）
map（映射）
在C++语言中，set 和 map 都分别提供了三种数据结构，每种数据结构的底层实现和用途都有所不同，例如什么时候用std::set，什么时候用std::multiset，什么时候用std::unordered_set，都是很有考究的。只有对这些数据结构的底层实现很熟悉，才能灵活使用，否则很容易写出效率低下的程序。
