最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 【LeetCode】从两数之和到四数之和(JS实现)

    正文概述 掘金(寒草)   2021-01-13   395

    背景

    从零开始的leetcode之路,刚刚开始就遇到了之前常常遇到的问题,两数之和,我也去回顾了我在一年之前写的代码。

    结果是毫无疑问的暴力破解。

    var twoSum = function(nums, target) {
        var arr=[];
        for(var i=0;i<nums.length-1;i++){
            for(var j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    arr.push(...[i,j]);
                    return  arr;
                }
            }
        }
    };
    

    【LeetCode】从两数之和到四数之和(JS实现)

    【LeetCode】从两数之和到四数之和(JS实现)【LeetCode】从两数之和到四数之和(JS实现)

    直接双重循环解决,执行用时也仅仅超过了11%的提交记录,顺便吐槽一下,我这push之后直接return是个什么操作?想了两个字,青涩。

    所以,我想现在去统一解决这类问题,虽然,现在的我也不一定可以想到最好的办法去解决两数之和,三数之和,四数之和,但是我想再过一年,我再回过头来看我现在写的文章,如果还能说出“我当时真是青涩”这几个字,说明我又成长了,也应该是不错的体验。

    (ps:我是菜鸡,思路和想法可能不能让大佬们满意,多多包涵~)

    两数之和

    题目

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。

    你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。可以按任意顺序返回答案。

    例子

    输入:nums = [2,7,11,15], target = 9
    输出:[0,1]
    解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
    

    【LeetCode】从两数之和到四数之和(JS实现)

    思路

    之前用的双重循环暴力破解肯定不行了,因为要返回的是下标,是一个 key->value的结构,所以我们可以顺理成章的想到借助Map去解决这个问题。

    我们写代码之前注意把逻辑理清:

    1. 首先,我们new一个Map,用于存储key和value的映射关系。
    2. 之后我们对数组进行遍历。
    3. 遍历会有两个情况:
    • 这个值之前在Map中出现过,表示,数组中存在重复数据,我们判断这个值的两倍是否是我们要的target。如果是,输出对应的下标,循环结束
    • 这个值之前没有在Map中出现过,我们去看 target-当前值 是否存在在Map中,如果存在,则输出对应的下标,循环结束,如果不存在,只需要把当前的 value和key存储在Map中就好。

    代码

    var twoSum = function(nums, target) {
        let map = new Map();
        for(let i=0;i<nums.length;i++){
            if(map.has(nums[i])){
               if( 2*nums[i] === target ){
                   return [map.get(nums[i]) , i];
               } 
            }else{
                if(map.has(target - nums[i])){
                    return [map.get(target - nums[i]) , i];
                }else{
                    map.set(nums[i] , i);
                }
            }
        }
    };
    

    【LeetCode】从两数之和到四数之和(JS实现)

    结果

    【LeetCode】从两数之和到四数之和(JS实现)【LeetCode】从两数之和到四数之和(JS实现)

    嗯,比一年前好多了,但是如何进一步提高运行效率还需要思考。

    三数之和

    题目

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。

    注意:答案中不可以包含重复的三元组。

    例子

    输入:nums = [-1,0,1,2,-1,-4]
    输出:[[-1,-1,2],[-1,0,1]]
    
    输入:nums = []
    输出:[]
    

    【LeetCode】从两数之和到四数之和(JS实现)

    思路

    原本我的想法很简单,两数之和的问题已经解了,那三数之和岂不就是,遍历数组,确定一个数A,对剩下部分的数组进行两数之和的操作,如果两数之和方法返回值有结果[B,C],那我们就可以把数组做个拼接,直接把[A,B,C] 返回就ok了。

    但是这回的问题有一点不同,我们找出的是所有的三元组,我本想对上面的 二数之和 进行改造,继续使用Map,但是发现在处理重复数据的时候比较困难,所以我想去寻找一种新的解决方案。

    首先,有那么一句至理名言:”犹豫不决先排序,步步逼近双指针“。

    这句话也给到了我思路,下面我说下思路:

    1. 按照上面至理名言所说,我们先排序,得到一个排好序的数组。
    2. 之后我们对数组进行遍历
    3. 如果nums[i]>0,又因为现在数组是按照从小到大排序,于是,以后不再出现可能的三元组,直接遍历结束
    4. 如果nums[i] === nums[i-1],则表示当前数值重复,因不可以出现重复三元组,直接continue跳过本次循环体后续操作
    5. 下面我们 设置Left = i+1;设置Right = length-1,就如前面所说的”步步逼近双指针“,我们从L到R进行循环,循环结束条件是Left<R
    6. 如果nums[i]+nums[Left]+nums[Right ]>0,则Right左移
    7. 如果nums[i]+nums[Left]+nums[Right ]<0,则Left右移
    8. 如果nums[i]+nums[Left]+nums[Right ]=0,将[nums[i],nums[Left],nums[Right ]] 追加到结果中去,并且我们这时为了避免重复,需要额外判断:如果nums[Left]==nums[Left+1],则L++;如果nums[Right ]===nums[Right -1],则Right --。
    9. 返回结果

    代码

    var threeSum = function(nums) {
        let length=nums.length;
        nums.sort((a,b)=>a-b);
        let res=[];
        for(let i=0;i<length;i++){
            if(nums[i]>0){
                return res;
            }
            if(i>0&&nums[i]===nums[i-1])
                continue;
            let Left=i+1;
            let Right=length-1;
            while(Left<Right){
                if(nums[i]+nums[Left]+nums[Right]==0){
                    res.push([nums[i],nums[Left],nums[Right]]);
                
                    while(Left<Right&&nums[Left]==nums[Left+1]){
                        Left++;
                    }
                    while(Left<Right&&nums[Right]===nums[Right-1]){
                        Right--;
                    }
                    Left++;
                    Right--;
                }
                
                else if(nums[i]+nums[Left]+nums[Right]>0){
                    Right--;
                }else{
                    Left++;
                }
            }
    
    
        }
        return res
    };
    

    【LeetCode】从两数之和到四数之和(JS实现)

    结果

    【LeetCode】从两数之和到四数之和(JS实现)【LeetCode】从两数之和到四数之和(JS实现)

    四数之和

    题目

    给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

    例子

    给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。
    
    满足要求的四元组集合为:
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]
    

    【LeetCode】从两数之和到四数之和(JS实现)

    思路

    最开始,我的想法很简单,这是所有满足情况的四元组,所以我比之前三数之和多一层遍历就好了,所以借用了三数之和的代码稍作改动,于是就有了下面这段代码

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[][]}
     */
    var threeSum = function(nums, target) {
        let length=nums.length;
        let res=[];
        for(let i=0;i<length;i++){
            if(nums[i]>target&&nums[i]>0){
                return res;
            }
            if(i>0&&nums[i]===nums[i-1])
                continue
            let Left=i+1
            let Right=length-1
            while(Left<Right){
                if(nums[i]+nums[Left]+nums[Right]==target){
                    res.push([nums[i],nums[Left],nums[Right]]);
                
                    while(Left<Right&&nums[Left]==nums[Left+1]){
                        Left++;
                    }
                    while(Left<Right&&nums[Right]===nums[Right-1]){
                        Right--;
                    }
                    Left++;
                    Right--;
                }
                
                else if(nums[i]+nums[Left]+nums[Right]>target){
                    Right--;
                }else{
                    Left++;
                }
            }
        }
        return res
    };
    var fourSum = function(nums, target) {
        let length=nums.length;
        nums.sort((a,b)=>a-b);
        let res=[];
        let tempArr = [];
        for(let i=0;i<length;i++){
            if(nums[i]>target&&nums[i]>0){
                return res;
            }
            if(i>0&&nums[i]===nums[i-1])
                continue
            tempArr = threeSum(nums.slice(i+1),target-nums[i]);
            if(tempArr.length>0){
                for(let item of tempArr){
                    res.push([nums[i],...item]);
                }
            }
        }
        return res;
    }
    

    【LeetCode】从两数之和到四数之和(JS实现)

    结果肯定也是不太好。

    【LeetCode】从两数之和到四数之和(JS实现)【LeetCode】从两数之和到四数之和(JS实现)

    所以我开始去重写代码,不去利用前面三数之和的代码,下面整理我的想法(代码逐行解析):

    1. 首先,我们还是需要对数组进行排序。
    2. 因为有四个数,我才用的是 双重循环(first,second)+双指针遍历(Left,Right)的方案,时间复杂度控制在O(n3)。
    3. 第一层循环,确定first指向的位置,和三数之和一样,如果nums[first]>target&&nums[first]>0,因为我们直接return.将结果返回。为了不出现重复结果,我们也会判断first>0&&nums[first]===nums[first-1]的结果,如果是true,直接将first右移(countinue)
    4. 第二层循环,确定second指向,如果nums[first]+nums[second]>target&&nums[second]>0,我们直接结束循环体(break),因为数组是从小到大排序的,后面的已经不需要再处理。当然,为了不出现重复结果,我们也会判断second>first+1&&nums[second]===nums[second-1]的结果,如果是true,直接second右移(continue)
    5. 下面进行双指针遍历,思路和前面的三数之和一样,只不过条件有些许变化。
    6. 我们设置 Left = second+1,Right = length-1。双指针遍历结束条件也依然是 Left<Right。
    7. 如果nums[first]+nums[second]+nums[Left]+nums[Right]>target,则Right左移
    8. 如果nums[first]+nums[second]+nums[Left]+nums[Right]<target,则Left右移
    9. 如果nums[first]+nums[second]+nums[Left]+nums[Right]=0,将[nums[first],nums[second],nums[Left],nums[Right]]追加到结果中去,并且我们这时为了避免重复,需要额外判断:如果nums[Left]==nums[Left+1],则L++;如果nums[Right ]===nums[Right -1],则Right --。
    10. 程序结束

    代码

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[][]}
     */
    var fourSum = function(nums,target){
        let length=nums.length;
        nums.sort((a,b)=>a-b);
        let res = [];
        let sumTemp = 0;
        for(let first=0;first<length-3;first++){
            if(nums[first]>target&&nums[first]>0){
                return res;
            }
            if(first>0&&nums[first]===nums[first-1]){
                continue;
            }
            for(let second=first+1;second<length-2;second++){
                if(nums[first]+nums[second]>target&&nums[second]>0){
                    break;
                }
                if(second>first+1&&nums[second]===nums[second-1]){
                    continue;
                }
                let Left=second+1;
                let Right=length-1;
                while(Left<Right){
                    sumTemp = nums[first]+nums[second]+nums[Left]+nums[Right];
                    if(sumTemp===target){
                        res.push([nums[first],nums[second],nums[Left],nums[Right]]);
                        while(Left<Right&&nums[Left]===nums[Left+1]){
                            Left++;
                        }
                        while(Left<Right&&nums[Right]===nums[Right-1]){
                            Right--;
                        }
                        Left++;
                        Right--;
                    }
                    else if(sumTemp>target){
                        Right--;
                    }else{
                        Left++;
                    }
                }
            }
        }
        return res;
    }
    

    【LeetCode】从两数之和到四数之和(JS实现)

    结果

    【LeetCode】从两数之和到四数之和(JS实现)【LeetCode】从两数之和到四数之和(JS实现)

    (ps:其实一般都是80%左右,90%是运气好)

    结语

    两数之和,三数之和,四数之和还是比较常见的问题,在这里做了统一的整理,运行结果还是可以接受的,整体的思路就是双指针遍历(两数之和用的是Map),如果后续思考找到更好的解题思路,再做后续的修改和补充。

    当然我也希望,一年之后我再看我之前写的思路,还会吐槽,”一年前的我真的是青涩“,这样。。哈哈


    起源地下载网 » 【LeetCode】从两数之和到四数之和(JS实现)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元