day07 四数相加Ⅱ 赎金信 三数之和 四数之和

题目1：454? 四数相加Ⅱ

题目链接：454 四数相加Ⅱ

题意

4个整数数组nums1， nums2，?nums3， nums4的长度均为n，有多少个元组（i，j，k，l）使得

nums[i]+nums[j]+nums[k]+nums[l]==0? ?（本题不包含去重的逻辑，i，j，k，l? 可以相等，一组元素与一组元素之间的各个元素也可以相等）

暴力解法

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count = 0;
        for(int i=0;i<nums1.size();i++){
            for(int j=0;j<nums2.size();j++){
                for(int k=0;k<nums3.size();k++){
                    for(int l=0;l<nums4.size();l++){
                        if(nums1[i]+nums2[j]+nums3[k]+nums4[l]==0){
                            count++;
                        }
                    }
                }
            }
        }
        return  count;
    }
};

会报如下超时错误

map

数组的数值较大且较为分散，所以数组可以排除

将4个元素分组，分成两组（这样的时间复杂度最低O(n^2)）nums1与nums2? nums3与nums4

看其中一组的元素和是否出现过，还要知道出现过的次数(value)，因此使用map

unordered_map的读写效率最高

步骤

① 遍历nums1和nums2，求解nums1[i]+nums2[j]的和，将这个和及其出现的次数放到map中

② 遍历nums3和nums4，在map中查询0-(nums3[k]+nums4[l])，

如果存在key==0-(nums3[k]+nums4[l])? 就将count加上key对应的value，这点很重要，一定要加value，因为这个key可能在nums1和nums中出现多种组合，这都是满足题目要求的！！！

例如:

nums1[1]+nums1[2]=5

nums1[1]+nums1[4]=5

nums1[3]+nums2[5]=5

nums3[1]+nums4[1]=-5

这种就是nums1[i]+nums2[j]在map中存在多种组合，key==5时，对应的value==3

因此，count=count+3

单纯下标

代码

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> map;//定义map，存放nums1[i]+nums2[j]
        int count = 0;
        for(int i=0;i<nums1.size();i++){
            for(int j=0;j<nums2.size();j++){
                map[nums1[i]+nums2[j]]++;
            }
        }
        for(int k=0;k<nums3.size();k++){
            for(int l=0;l<nums4.size();l++){
                int target = 0 - (nums3[k]+nums4[l]);
                if(map.find(target)!=map.end()){
                    count += map[target]; //加上target（即nums[i]+nums[j]）出现的次数
                }
            }
        }
        return count;
    }
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^2

简便

代码

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

• 时间复杂度: O(n^2)
• 空间复杂度: O(n^2)，最坏情况下A和B的值各不相同，相加产生的数字个数为 n^2

以上解法和有效字母异位词比较相像，都是先遍历数组，对哈希表进行插入操作；再遍历另外的数组，在哈希表中进行查询操作

题目2：赎金信

题目链接：383 赎金信

题意

判断ransomNote字符串能否由magazine字符串中的字符组成，二者均由小写英文字母构成，但是magzine中的每个字符只能使用1次，这两点很关键

即判断ransomNote字符串中的字符是否在magazine中出现过，因此使用哈希表

数组

由于两个字符串中的元素只包含小写字母，是连续的，是有限值且有有限个，因此想到使用数组

步骤

① 一定要先遍历magazine字符串（因为是在magazine字符串中查找ransomNote中的字符是否存在），统计magazine字符串中每个字符出现的次数（每个字符只能使用1次），记录在hash数组中；

② 再遍历ransomNote字符串，在上述统计的次数的基础上，遇到相同的字符，在hash数组中对应元素做减减的操作；

③ 最后遍历hash数组，看是否有小于0的元素，若出现小于0的元素，证明ransoNote字符串中的对应该字符数量多于magazine字符串中该字符的数量，说明ransomNote字符串不能由magazine字符串中的字符组成

代码

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

• 时间复杂度: O(n)
• 空间复杂度: O(1)，hash数组的大小是常数

代码也可以这样写，hash减减后，直接判断hash中该元素是否小于0，若小于0的话，直接return false即可，就不用后面的hash元素再继续减减操作了

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

• 时间复杂度: O(n)
• 空间复杂度: O(1)，hash数组的大小是常数

暴力解法（不推荐）

如果遇到magazine[i]==ransomNote[i]，就将ransomNote中的该字符删掉，同时一定要使用break跳出这个内部for循环，因为magazine中的一个字符只能匹配ransomNote中的1个字符，如果匹配上了，那么这个字符就废了，不能再重复使用了，需要继续下一个magazine元素的循环

代码

！！！注意break的使用

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
       for(int i=0;i<magazine.size();i++){
           for(int j=0;j<ransomNote.size();j++){
               if(magazine[i]==ransomNote[j]){
                   ransomNote.erase(ransomNote.begin()+j);
                   break;//这里一定要break,因为magazine[i]已经和ransomNote[j]匹配了，再往下让magazine[i]匹配元素不满足要求       
                         //（magazine中的字符只能在ransomNote中使用1次），所以使用break跳出这层内部for循环，继续i++下一个magazine的元素
               }
           }
       }
       if(ransomNote.size()==0){
           return true;
       }else{
           return false;
       }
    }
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

题目3：15 三数之和

题目链接：15 三数之和

题意

1个整数数组nums ，找出nums[i]+nums[j]+nums[k]==0的[i，j，k]的组合，其中i，j，k互不相等（意味着元素不能重复使用）一组中的nums[i],nums[j],nums[k]的组合不能和另一组中的nums[i],nums[j],nums[k]完全相同，比如：0 1 -1 和 1 0 -1这就重复了，所以需要去除一组

去重是关键

哈希法（不推荐）

使用哈希表去重细节较多

双指针法

不可以先将数组中相同的元素删除，因为可能会使得一些满足条件的组合消失，例如：2 2 -4?

开始时一定要对数组进行排序?

逻辑反例

例1，nums[left]，nums[right]去重放置的位置

是和nums[i]一样，放在前面，还是放在while循环的最后面

例2，是先移动left,right还是先去重

这里在写代码时，产生了矛盾，当元素组合满足条件时，到底是先移动还是先去重呢？

丢掉解

重复解

例3，if(nums[i]==nums[i-1]){}，{}里是i++，还是continue

想的比较单纯：遇到重复值，我跳过去，不就OK了嘛，但是事实不是这样，有可能有连续的多个重复的值，所以使用i++就产生了错误

例4，如果跳过了重复值，会不会错过一些遍历重复值过程中的组合呢

例5? nums[left] nums[right]去重逻辑里面while循环加入right>left

如果不加right<left的限制会报如下错误

代码

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++){
            //nums[i]剪枝 一级剪枝
           if(nums[i]>0){
               return result;//这里是return result 不能return {}，在此之前可能已经有结果了
               //break;//这里使用break，也是一样的，直接return结果，结束这个for循环
           }
           //nums[i]去重  一级去重
           if(i>0 && nums[i]==nums[i-1]){
               continue;//继续下一次循环
               //注意这里continue不能写i++,因为要是写i++的话，对于连续3个相同的数字，会算两遍，看反例3
           }
           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]});
                   //去重去的是满足条件的相同的组合，因此，要放在else里面
                   while(right>left && nums[right]==nums[right-1]){
                        right--;
                    }
                   while(right>left && nums[left]==nums[left+1]){
                        left++;
                    }
                   left++;//一定要在去重之后再移动left和right两个指针
                   right--;
               } 
           }
       }
       return result;
    }
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

题目4：18 四数之和

题目链接：18 四数之和

题意

整数数组nums的长度为n，返回nums[a]+nums[b]+nums[c]+nums[d]==target的元组[nums[a],nums[b],nums[c],nums[d]]，其中a，b，c，d互不相等（意味着元素不能重复使用），返回的元组不能重复，但元组内部的元素可以重复（因为数组nums中可能存在重复的元素）

双指针法

和上题三数之和一样，同样使用双指针法解决

剪枝的时候要注意，因为target可正可负可零，所以剪枝逻辑就不能像三数之和那样，直接判断nums[i]>target就行了，若target可能为负数，若nums[i]>target，若nums[i+1]还是负数，那么nums[i]+nums[i+1]<nums[i]，可能会出现四数之和等于target的情况，如下例：

1) 对于一级剪枝，所以一级剪枝要确定target>0&&nums[i]>target

同样地，对于二级剪枝，也要注意这些细节，二级剪枝时，将nums[i]+nums[j]视作一个整体，与target进行判断

流程

代码

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 && target>=0){
                //if(nums[i]>target && (target>=0 || nums[i]>=0))
                return result;
            }
            //一级去重
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            for(int j=i+1;j<nums.size();j++){
                //二级剪枝 将nums[i]+nums[j]看作一个整体
                if(nums[i]+nums[j]>target && target>=0){
                    //if(nums[i]+nums[j]>target && (target>=0 || nums[i]+nums[j]>=0))
                    break;
                }
                //二级去重
                if(j>i+1 && nums[j]==nums[j-1]){
                    continue;
                }
                int left = j + 1;
                int right = nums.size() - 1;
                while(right>left){
                    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]});
                        //nums[left] nums[right]去重
                        while(right>left && nums[left]==nums[left+1]){
                            left++;
                        }
                        while(right>left && nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
};

• 时间复杂度: O(n^3)
• 空间复杂度: O(1)