[数据结构与算法]代码随想录训练营第7天|LeetCode ：454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

参考

代码随想录

题目一：454.四数相加II

看了题目之后只想到了暴力解法，但是暴力解法时间复杂度太高。代码随想录给出的解题步骤如下：

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 就可以了

看了上面的解题步骤之后，总结一下自己的理解：题目给出了四个数组，把四个数组分成两组，AB为一组，CD为一组（怎么分组都可以），然后遍历A和B，将a+b的和以及出现的次数放入map中，和为key，次数为value，然后再遍历C和D，查找-(c+d)是否则map中出现，若有，则对应的value就是出现的次数。
代码实现如下：

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

看了解题思路之后代码还是很好写的，没有什么太大的难点。

题目二：83. 赎金信

一、按照自己的想法实现

看了题目之后第一感觉是不难，用map来统计magazine中的字符及出现的次数（字符作为key，字符出现的次数作为value），然后遍历ransomNote，如果能在map找到对应的字符且其出现的次数大于0，则将该字符出现的次数减1，否则说明缺少相关字符，直接返回false。代码实现如下：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<int,int>  mp;
        for(char ch:magazine)   mp[ch]++;
        for(char ch:ransomNote)
        {
            if(mp.find(ch) != mp.end() && mp[ch] > 0)
                mp[ch]--;
            else
                return false;
        }
        return true;
    }
};

二、参照代码随想录的实现方法

代码随想录提供了两种方法，暴力求解和哈希解法，暴力求解无非就两层循环，哈希解法用数组来实现而不是map，这样效率更高，更省空间。注意题目中的信息，两个字符串都是由小写字母组成，因此可以定义一个长度为26的数组来统计每个字符出现的次数，具体的代码实现如下：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int cnt[26] = {0};
        for(char ch:magazine)   cnt[ch - 'a']++;
        for(char ch:ransomNote) 
            if(cnt[ch-'a'] > 0) cnt[ch-'a']--;
            else    return false;
        return true;
    }
};

相比之下，用数组实现要更简洁，效率更高。

小结

在C++中有三种方式（数组、集合和映射）实现哈希结构，要注意选取，能够用数组实现的尽量选用数组，效率更高，占用的空间更小。

题目三：15. 三数之和

这个题尝试暴力求解，即三层循环，但是不能全部通过，原因在与会有重复的情况存在，当然可以对结果去重，但是这样的解法时间复杂度实在太高了。代码随想录里给出了两种方法，哈希法和双指针法，但是哈希法依然存在重复问题，而且去重问题本身也是一个复杂的问题，所以这里只学习双指针的解法。
双指针法的解题思路：先对数组从小到大进行排序，指针i遍历数组，left = i+1,right = nums.size()-1，sum = nums[i]+nums[left]+nums[right]，如果nums>0，则需要往左移动rigth指针，这样才有可能使和减小；若sum<0，则需要往右移动left指针，才有可能使和变大。这里说有可能是因为存在重复的情况，所以移动之后和可能仍然不变。同样，每次移动任意一个指针后都要确保没有重复，这也就是去重的过程。例如，对于数组{-4,-1,-1,0,1,2}，当从i = 1到i = 2时，由于nums[2] = nums[1]，所以必须跳过i = 2，否则得到的结果就会重复，left和right也同样需要去重，都是与上一次进行比较，若相同，则跳过。另外需要注意的是，对于确定的i，可能存在多个left和right的组合满足条件，因此对于确定的i，循环查找的条件是 left < right（不能包含等号）。具体的代码实现如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++)
        {
            if(i > 0 && nums[i] == nums[i-1])   continue; //对i去重
            int left = i+1;
            int right = nums.size()-1;
            while(left < right)  //对于每一个i，可能有多个left和right的组合满足条件，所以要
            {                   //直到left == right才结束一次查找
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0 && left < right)    res.push_back({nums[i],nums[left],nums[right]});
                if(sum > 0) //往左移动right
                    do{     //要保证移动后的left与上一个left没有重复
                        right--;
                    }while(left < right && nums[right] == nums[right+1]); 
                else   //往右移动left
                    do{ //要保证移动后的right与上一个right没有重复
                        left++;
                    }while(left < right && nums[left] == nums[left-1]) ;          
            }
        }
        return res;
    }
};

代码随想录中的去重逻辑的思考还是很有启发性的，特别是i的去重。另外，在循环的开始可以增加一条语句进行剪枝： if (nums[i] >0) return result;

题目四：18. 四数之和

上一个题是三个数，这个题变成了四个数，那无非就是在上一个题的基础上再一个for循环，但是思路上没有错，但是提交的时候部分用例测试的时候数据溢出了，代码如下：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int j=0;j<nums.size();j++)
        {
            if(j > 0 && nums[j] == nums[j-1])   continue;   //对j去重
            for(int i=j+1;i<nums.size();i++)
            {
                if(i > j+1 && nums[i] == nums[i-1])   continue; //对i去重
                int left = i+1;
                int right = nums.size()-1;
                while(left < right)  //对于每一个i，可能有多个left和right的组合满足条件，所以要
                {                   //直到left == right才结束一次查找
                    int sum = nums[j] + nums[i] + nums[left] + nums[right];
                    if(sum == target && left < right)    
                        res.push_back({nums[j],nums[i],nums[left],nums[right]});
                    if(sum > target) //往左移动right
                        do{     //要保证移动后的left与上一个left没有重复
                            right--;
                        }while(left < right && nums[right] == nums[right+1]); 
                    else   //往右移动left
                        do{ //要保证移动后的right与上一个right没有重复
                            left++;
                        }while(left < right && nums[left] == nums[left-1]) ;          
                }
            }
        }
        return res;
    }
};

当输入的数组为[1000000000,1000000000,1000000000,1000000000]（都是10^9）的时候，在int sum = nums[j] + nums[i] + nums[left] + nums[right];这条语句上报错了，很明显是数据溢出了。尝试把sum的类型改为long，但还是报错，原因在于要一次计算完成之后才能转换，所以，应该把sum改成long类型的同时，把任意一个加数强制转换为long类型，这样计算的时候其他加数也就自动转化了。求和语句改为:

long sum = (long)nums[j] + nums[i] + nums[left] + nums[right];

这样就能通过了。但是其实还可以进行一些剪枝操作，在每层循环的开始先进行初步判断，分别添加一下语句：

if(nums[j] > target && nums[j] >=  0)   break;  //剪枝

if(nums[i]+nums[j] > target && nums[i] + nums[j] >= 0)  break;   //剪枝

这样可以进一步减少程序的运行时间。上面的判断中不能只判断nums[j] > target就结束，因为target可正可负，例如target = -10，而nums[j] = -4，虽然nums[i] > target，但是四个数相加之后和完全有可能等于target，这里是一个易错点。

今日小结

今天的题不怎么会做，但是看了题解还是很好理解的。三数之和和四数之和这两个题的解题思路是一致的，如果是更多的数相加也是同样的解法，用双指针可以降低复杂度，三数之和中从O(n^3) 降低为O(n^2) ，四数之和从O(n^4 )降低为O(n^3) 。今天的题的解法包括了哈希法和双指针法，有时候可以结合着用。