前言
今天的四道题目稍稍有点难度，需要理解和反复记忆才行。四数相加类比于两数之和，赎金信类比于异位词，三数之和和四数之和自成体系，可以推广到n数之和。
Leetcode 454 四数相加Ⅱ
题目链接：454. 四数相加 II - 力扣（LeetCode）
代码随想录题解：代码随想录 (programmercarl.com)
思路：类比于两数之和，在一个map里放前两个数组所有和的出现次数，再遍历后两个数组检查所需要的和是否出现就行了，而且不用去重，如果需要去重就会麻烦很多。
代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4)
{
unordered_map<int,int> res;
int count=0;
for(int i:nums1)
{
for(int j:nums2)
{
res[i+j]++;//记录前两个数组的和出现的次数
}
}
for(int i:nums3)
{
for(int j:nums4)
{
count+=res[-(i+j)];//遍历后两个数组 寻找有没有匹配的
}
}
return count;
}
};Leetcode 383 赎金信
题目链接：https://leetcode.cn/problems/ransom-note/
代码随想录题解：代码随想录 (programmercarl.com)
思路：和异位词差不多，都是桶排序记录一个字符串中的字母情况，再用另一个字符串检查即可。这个题目不一样的地方是问a字符串能否组成b字符串，所以需要先统计a字符串的字母情况，然后用b字符串来取，如果取的时候发现数量不够了那就是无法组成。异位词则是严格判断两个字符串字母的出现情况是否一样，此时先后顺序就不那么重要了。
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int a[30]={0};
if (ransomNote.size() > magazine.size())
{
return false;
}
for(int i=0;i<magazine.size();i++)
{
a[magazine[i]-'a']++; //先统计a字符串
}
for(int i=0;i<ransomNote.size();i++)
{
a[ransomNote[i]-'a']--;//b字符串来拿取
}
for(int i=0;i<26;i++)
{
if(a[i]<0) //数量不够了
{
return false;
}
}
return true;
}
};Leetcode 15 三数之和
代码随想录题解：代码随想录 (programmercarl.com)
思路：（这道题目的target是0）去重是关键！采用双指针法，为什么不用哈希法是因为去重太难写了。这里文字描述太困难，拿代码随想录的一张动图就很明白了，但需要记得排序。下面是重要的去重逻辑：第一步，如果第一个数都比0大那证明肯定没有满足条件的情况了，直接return。第二步，如果第一个数和第二个数是一个数肯定不行（-1，-1，1，0），但注意是运作到第二个数的时候和第一个数比，所以写法是Nums[i]==nums[i-1]。第三步，left和right的去重(-1，1，1，2，-2，-1，-1)，结合这个例子理解代码就很容易了，代码实现的是只会统计重复出现中的最后一组数据，在最后还要记得left和right各自的移动，因为已经装入结果了。
代码：
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)//第一步 第一个数都大于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({nums[i],nums[left],nums[right]});
while(left<right&&nums[right]==nums[right-1]) //第三步 right
{
right--;
}
while(left<right&&nums[left]==nums[left+1]) //第三步left
{
left++;
}
right--; //记得装进去之后要移动left和right
left++;
}
}
}
return result;
}
};Leetcode 18 四数之和
代码随想录题解：代码随想录 (programmercarl.com)
思路：（这道题目target不是0！）类比三数之和，只不过多了一个数，多了一个指针，也就多了一次循环。去重逻辑中left和right不变，只不过因为target不是0所以第一步的写法要多加一个判断就是均为正数，在对第二个数去重的时候其实就是把两个数看成一个整体去重。具体的见代码
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]>target&&nums[i]>=0)//因为target不再是0 所以都要大于0
{
break;//记得要写成break
}
if(i>0&&nums[i]==nums[i-1])//本次的数不能和上一次一样
{
continue;
}
for(int j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]>target&&nums[i]+nums[j]>=0)//第二次去重 将和看为一个整体
{
break;//记得要写成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[right]==nums[right-1])//right去重
{
right--;
}
while(left<right&&nums[left]==nums[left+1])//left去重
{
left++;
}
right--;//记得移动right和left
left++;
}
}
}
}
return result;
}
};
C++ const
const关键字代表不变，即被const关键字修饰的某个东西是不能被改变的。如果某个函数不想修改传进来的参数，就用const修饰；如果一个成员变量或者对象不想被改变，那就用const修饰。注意用const修饰的变量一定要在声明的时候就初始化。需要区分的是指针常量和常量指针。
常量指针(pointer to a constant)：证明这个指针是指向常量的，不能通过指针修改这个常量，但可以修改指针指向的地址。
指针常量(constant pointer)：说明指针是一个常量，不能修改指针指向的地址，但可以通过指针修改其指向的内容。
顶层const与底层const
const 在 * 号 左侧的为 底层 const => 指针常量 => 指针存储的地址不可被修改
const 在 * 号 右侧的为 顶层 const => 常量指针 => 指针指向的对象不可被修改
总结
今天把STL的视频看完了，明天要继续看C++内存管理的视频，miniSTL要提上日程了。
标签：四数,const,nums,int,随想录,vector,Leetcode,指针 From： https://blog.csdn.net/m0_74853141/article/details/140641398