代码随想录第55期训练营第七天|LeetCode454.四数相加II、383.赎金信、15.三数之和、18.四数之和
前言
这是我参加的第二次训练营！！！爽！这次我将更加细致的写清每一道难题，不仅是提升自己，也希望我自己的写的文章对读者有一定的帮助！
打卡代码随想录算法训练营第55期第七天（づ￣3￣）づ╭❤～
首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第55期的训练营大家庭一起进步。
今日题目
在学习今天题目之前，可以先去学习一下：哈希表理论基础
LeetCode 454 四数相加II
题目链接：454 四数相加II
文章讲解：四数相加II
视频讲解：卡哥讲解 —— 四数相加II
本题是对map的使用，这题乍一看暴力算法直接就是O(n^4)，但是我们通过先算前两个再算后两个可以将其时间复杂度缩短到O(n^2)，将前两个数的结果用map存起来，因为本题要存结果和个数，所以使用map是最优的。
public class Solution {
public int FourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//字典dic的键存储nums1 + nums2的值 dic的值为相加为键的个数
Dictionary<int,int> dic = new Dictionary<int,int>();
int res = 0;
//先计算nums1和nums2的所有结果
foreach(var num1 in nums1)
{
foreach(var num2 in nums2)
{
int temp = num1 + num2;
if(dic.ContainsKey(temp))
dic[temp]++;
else
dic.Add(temp , 1);
}
}
//再计算nums3和nums4的所有结果
foreach(var num3 in nums3)
{
foreach(var num4 in nums4)
{
int temp = num3 + num4;
//此处只要相反那么相加就为0
if(dic.ContainsKey(-temp))
res += dic[-temp];
}
}
return res;
}
}LeetCode 383 赎金信
题目链接：383 赎金信
文章讲解：赎金信
本题相对简单，一看就是需要存储两个值的变量，直接想到map来解决。
public class Solution {
public bool CanConstruct(string ransomNote, string magazine) {
//dic中存储magazine中每一个单词以及出现的次数
Dictionary<char,int> dic = new();
//存储字典
for(int i = 0; i < magazine.Length; i++)
{
if(dic.ContainsKey(magazine[i]))
dic[magazine[i]]++;
else
dic.Add(magazine[i] , 1);
}
for(int i = 0; i < ransomNote.Length; i++)
{
if(dic.ContainsKey(ransomNote[i]))
{
dic[ransomNote[i]]--;
//每次出现-1 如果出现负数则代表magazine中的某一个字符个数没有ransomNote中的多
if(dic[ransomNote[i]] < 0)
return false;
}
//如果不存在 直接false
else
return false;
}
return true;
}
}LeetCode 15 三数之和
题目链接：15 三数之和
文章讲解：三数之和
视频讲解：卡哥讲解 —— 三数之和
这题使用双指针的思路，先将一个数进行固定，剩下的数进行两边寻值。
本题的一大难题是去重，一大亮点是剪枝，去重的关键是理解去掉什么重复，是组合中内容的重复，还是重复组合，如果使用 i 和 i + 1进行去重，去掉的是一个组合中的相同元素，而我们这种i 和 i - 1才是去掉重复组合，大家可以模拟一下。
其次就是剪枝，在大循环中的nums.Length - 2是因为如果超过这个数，后面连两个数都没有了，哪还有三数之和，其次就是在一开就确定最小的数是否大于0，也能省掉不少无意义的计算。
public class Solution {
public IList<IList<int>> ThreeSum(int[] nums) {
List<IList<int>> res = new();
Array.Sort(nums);//这道题要去重，所以一定要排序
for(int i = 0; i < nums.Length - 2/*这里可以不写-2 只是这样剪枝会更省一点*/; i++)
{
//当最小的数都超过0 那后面的数不用看了
if(nums[i] > 0)
break;
//大循环去重，着重强调这里使用 i 和 i - 1进行比较
//是因为题目说的是不能出现重复组合，组合中是可以有重复元素的
if(i != 0 && nums[i] == nums[i - 1])
continue;
int num1 = nums[i];
int left = i + 1;
int right = nums.Length - 1;
int num2;
int num3;
//下面逻辑很好理解 少了就加 多了就减
while(left < right)//这里使用left < right 因为left和right永远不可能是同一个位置
{
num2 = nums[left];
num3 = nums[right];
int sum = num1 + num2 + num3;
if(sum < 0)
left++;
else if(sum > 0)
right--;
else
{
res.Add(new List<int>{num1 , num2 , num3});
//这里一定要注意 去重！
while(nums[left] == num2 && left < right)
left++;
while(nums[right] == num3 && left < right)
right--;
}
}
}
return res;
}
}LeetCode 18 四数之和
题目链接：18 四数之和
文章讲解：四数之和
视频讲解：卡哥讲解 —— 四数之和
本题和三数之和几乎一样，只是多了一个数，那么我们就多一个循环来多确定一个数即可。如果难以理解，就多做几遍，看看视频，看看代码随想录的内容。
public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
List<IList<int>> res = new();
Array.Sort(nums);//排序
//第一个确定的数
for(int i = 0; i < nums.Length - 3/*剪枝*/; i++)
{
if(i > 0 && nums[i - 1] == nums[i])//去重
continue;
//剪枝
if(nums[i] > target && target > 0)
break;
if(nums[i] > 0 && target < 0)
break;
int num1 = nums[i];
//第二个确定的数
for(int j = i + 1; j < nums.Length - 2/*剪枝*/; j++)
{
if(j > i + 1 && nums[j - 1] == nums[j])//去重
continue;
//剪枝
if(num1 + nums[j] > target && target > 0)
break;
if(num1 + nums[j] > 0 && target < 0)
break;
int num2 = nums[j];
//双指针
int left = j + 1;
int right = nums.Length - 1;
int num3;
int num4;
while(left < right)//用<是因为left 和 right 不可能指向同一个数
{
num3 = nums[left];
num4 = nums[right];
int sum = num1 + num2 + num3 + num4;
if(sum > target)
right--;
else if(sum < target)
left++;
else
{
res.Add(new List<int>{num1,num2,num3,num4});
while(left < right && nums[left] == num3)
left++;
while(left < right && nums[right] == num4)
right--;
}
}
}
}
return res;
}
}确实是个懒B，鸽了太久了，之后每天尽量2 - n更，争取把缺失的补回来，今天的难点是三数之和和四数之和，主要先理解双指针的解法，其次是如何去重，去什么样的重，怎样去重，最后理解透彻后，再进行锦上添花的剪枝操作。