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

这篇具有很好参考价值的文章主要介绍了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;
    }
};

会报如下超时错误

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

单纯下标

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

代码文章来源地址https://www.toymoban.com/news/detail-819722.html

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
简便

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

代码

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字符串中的字符组成

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

代码

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元素的循环

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

代码

!!!注意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 

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

逻辑反例
例1,nums[left],nums[right]去重放置的位置

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

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

丢掉解

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

重复解

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

代码

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

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

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

流程

day07 四数相加Ⅱ 赎金信 三数之和 四数之和,算法,leetcode,动态规划

代码

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)

到了这里,关于day07 四数相加Ⅱ 赎金信 三数之和 四数之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【代码随想录06】454. 四数相加 II 383. 赎金信 15. 三数之和 18. 四数之和

    题目描述 给你四个整数数组 nums1 、 nums2 、 nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 做题思路 本题可以使用哈希表, key 为 nums1[i] + nums2[j] 的和, value 为其出现的次数。然后再遍历 nums3 和

    2024年01月16日
    浏览(45)
  • C++刷题第六天 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

    给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 这个题目是哈希表应用的经典题目。 如果用暴力解法,四个数组,那肯定要四层for循环嵌套,时间复杂度就是n的四次方

    2024年02月13日
    浏览(46)
  • 代码随想录-哈希表02 第454题.四数相加II&383. 赎金信&第15题. 三数之和&第18题. 四数之和

    第454题.四数相加II 第454题.四数相加II 条件:四个数组中分别取一个,相加和为0,求满足条件的元组个数 思路使用1个map,mapA保存 s1 s2中相加和及其出现次数 遍历s3 s4,去判断是否满足 0 - (s3[i] + s4[j]) 在mapA中,并统计出现次数 383. 赎金信 383. 赎金信 题目要求,s1 是否能由s

    2024年02月12日
    浏览(45)
  • 【算法】排序+双指针——leetcode三数之和、四数之和

    三数之和 (1)排序+双指针   算法思路: 和之前的两数之和类似,我们对暴力枚举进行了一些优化,利用了 排序+双指针 的思路:   我们先排序,然后固定⼀个数 a ,接着我们就可以在这个数后面的区间内,使用之前两数之和使用的算法,快速找到两个数之和和固定的

    2024年02月13日
    浏览(53)
  • 【算法挨揍日记】day04——15. 三数之和、18. 四数之和

      15. 三数之和 https://leetcode.cn/problems/3sum/ 给你一个整数数组  nums  ,判断是否存在三元组  [nums[i], nums[j], nums[k]]  满足  i != j 、 i != k  且  j != k  ,同时还满足  nums[i] + nums[j] + nums[k] == 0  。请你返回所有和为  0  且不重复的三元组。 注意: 答案中不可以包含重复的三元

    2024年02月09日
    浏览(55)
  • leetcode两数、三数、四数之和

    如有错误,感谢不吝赐教、交流 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返

    2023年04月23日
    浏览(73)
  • 【代码随想录 | Leetcode | 第九天】哈希表 | 快乐数 | 四数相加 II | 赎金信

    欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来哈希法~快乐数 | 四数相加 II | 赎金信的分享 ✨ ✨题目链接点这里 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后

    2024年02月13日
    浏览(52)
  • 【代码随想录 | Leetcode | 第十天】哈希表 | 三数之和 | 四数之和

    欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来哈希法~三数之和 | 四数之和的分享 ✨ ✨题目链接点这里 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为

    2024年02月15日
    浏览(42)
  • 【算法专题--双指针算法】leecode-15.三数之和(medium)、leecode-18. 四数之和(medium)

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年04月09日
    浏览(49)
  • 2023-07-15 LeetCode每日一题(四数之和)

    点击跳转到题目位置 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且 不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 = a, b, c, d n a、b、c 和 d 互不相同 nums[a] + nums[b]

    2024年02月16日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包