代码随想录算法训练营第七天|LeetCode454. 四数相加 II，LeetCode383. 赎金信，LeetCode15. 三数之和，LeetCode18. 四数之和

LeetCode454. 四数相加 II

题目链接：454. 四数相加 II – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：学透哈希表，map使用有技巧！LeetCode：454.四数相加II_哔哩哔哩_bilibili 

思路：这个题很自然可以想到一个四层循环的思路，那样做时间复杂度是o(n^4)，会超时，所以是不对的。正确的做法可以化为两个二层循环，这样可以把时间复杂度降至o(n^2)。先把a+b作为key，而a+b出现的次数作为value，存入map中。然后在另一个二层循环中找map是否有0-(c+d)，如果有就在总的count上加上对应的value。

代码：

class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int>map;
for(int a:nums1){
for(int b:nums2){
map[a+b]++;
}
}
int count=0;
for(int c:nums3){
for(int d:nums4){
if(map.find(0-(c+d))!=map.end()){
count+=map[0-(c+d)];
}
}
}
return count;
}
};

LeetCode383. 赎金信

题目链接：383. 赎金信 – 力扣（LeetCode） 文章讲解：代码随想录

思路：这道题用哈希表的思路解决很简单，只需要用一个26个大小的数组来存储，然后把magazine的所有字母存入这个数组，然后再遍历ransomNote，每遍历一个字母就在数组中该数组字母的对应次数减一，如果在遍历过程中，发现数组中某一项为负数了，就return false，如果一直正常遍历就return true。

代码：

class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int>vec(26);
if(ransomNote.size()>magazine.size()){
return false;
}
for(int i=0;i<magazine.size();i++){
vec[magazine[i]-'a']++;
}
for(int i=0;i<ransomNote.size();i++){
vec[ransomNote[i]-'a']–;
if(vec[ransomNote[i]-'a']<0){
return false;
}
}
return true;
}
};

LeetCode15. 三数之和

题目链接：15. 三数之和 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：梦破碎的地方！| LeetCode：15.三数之和_哔哩哔哩_bilibili

思路：这是一道比较复杂的题，用哈希表会很麻烦。用双指针会简便一些，大体的思路是先确定第一个数的值，然后第二个第三个数分别用双指针向和为0靠拢。这个题最麻烦的点是去重，我的想法是第一个值用最左边的值，如果后续遇到的值和左边的一样就跳过，第二个和第三个反而是要接近中间的值（其实我觉得这里用更靠边的值也没有问题） 。

代码：

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(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){
left++;
}
else if(nums[i]+nums[left]+nums[right]>0){
right–;
}
else{
//第二个数的去重，如果是相同值我们只要最右边的那个
while(left<right&&nums[left]==nums[left+1]){
left++;
}
//第三个数的去重，如果是相同值我们只要最左边的那个
while(left<right&&nums[right]==nums[right-1]){
right–;
}
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
left++;
right–;
}
}
}
return result;
}
};

LeetCode18. 四数之和

题目链接：18. 四数之和 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：难在去重和剪枝！| LeetCode：18. 四数之和_哔哩哔哩_bilibili

思路：其实和三数之和基本一样，只不过外面又套了一层循环，然后此外，在和target比大小的时候由于nums数组中的值太大，需要转化为long类型，别的就没有区别了。

代码：

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(i>0&&nums[i]==nums[i-1]){
continue;
}
for(int k=i+1;k<nums.size();k++){
if(k>i+1&&nums[k]==nums[k-1]){
continue;
}
int left=k+1;
int right=nums.size()-1;
while(left<right){
if((long)nums[i]+nums[k]+nums[left]+nums[right]<target){
left++;
}
else if((long)nums[i]+nums[k]+nums[left]+nums[right]>target){
right–;
}
else{
while (right > left && nums[left] == nums[left + 1]){
left++;
}
while (right > left && nums[right] == nums[right – 1]){
right–;
}
result.push_back(vector<int>{nums[i],nums[k],nums[left],nums[right]});
left++;
right–;
}
}
}
}
return result;
}
};