JS算法题之三数之和入门基础_算法题基础知识教程

题目描述给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],满足要求的三元组集合为:
[[-1, 0, 1],[-1, -1, 2]
]解

JS算法题之三数之和入门基础

题目描述

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

JS算法题之三数之和入门基础_算法题基础知识教程

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答

这题我们才用排序+双指针的思路来做,遍历排序后的数组,定义指针l和r,分别从当前遍历元素的下一个元素和数组的最后一个元素往中间靠拢,计算结果跟目标对比。

<span type="button" data-toggle="tooltip" data-placement="top" data-clipboard-text="var threeSum = function(nums) {
if(nums.length a – b);
for(let i = 0; i 0 && nums[i] == nums[i-1]){
// 去重
continue;
}
if(nums[i] > 0){
// 若当前元素大于0,则三元素相加之后必定大于0
break;
}
// l为左下标,r为右下标
let l = i + 1; r = nums.length – 1;
while(l<r){
let sum = nums[i] + nums[l] + nums[r];
if(sum == 0){
res.push([nums[i], nums[l], nums[r]]);
while(l < r && nums[l] == nums[l+1]){
l++
}
while(l < r && nums[r] == nums[r-1]){
r–;
}
l++;
r–;
}
else if(sum 0){
r–;
}
}
}

return res;
};” title=”” data-original-title=”复制”>

var threeSum = function(nums) {
    if(nums.length < 3){
        return [];
    }

    let res = [];
    // 排序
    nums.sort((a, b) => a - b);
    for(let i = 0; i < nums.length; i++){
        if(i > 0 && nums[i] == nums[i-1]){
            // 去重
            continue;
        }
        if(nums[i] > 0){
            // 若当前元素大于0,则三元素相加之后必定大于0
            break;
        }
        // l为左下标,r为右下标
        let l = i + 1; r = nums.length - 1;
        while(l<r){
            let sum = nums[i] + nums[l] + nums[r];
            if(sum == 0){
                res.push([nums[i], nums[l], nums[r]]);
                while(l < r && nums[l] == nums[l+1]){
                    l++
                }
                while(l < r && nums[r] == nums[r-1]){
                    r--;
                }
                l++;
                r--;
            }
            else if(sum < 0){
                l++;
            }
            else if(sum > 0){
                r--;
            }
        }
    }

    return res;
};
海计划公众号
(0)
上一篇 2020/03/29 01:41
下一篇 2020/03/29 01:41

您可能感兴趣的内容

  • Popcorn.js教程视频_一个针对HTML5媒体的JavaScript事件框架

    Popcorn.js教程视频 GitHub:https://github.com/menismu/popcorn-js 简介描述:一个针对HTML5媒体的JavaScript事件框…

    2020/03/06
  • 简单高效实现一个按需加载图片的逻辑小白指南_加载使用攻略

    需求:根据页面滚动,当图片进入视野,就开始加载,否则不加载任何图片。代码://页面加载完成时先调用一下,首屏内的图片。
    loadImg();
    document.addEventListener(‘scroll’, function(e) {//跟着滚动,继续加载剩下的图片loadImg()
    })function loadImg(){//slice可以将类数组

    2020/03/26
  • Development模式是如何运作的?小白攻略_模式小白知识

    如果您的JavaScript代码库非常复杂,那么您可能会想办法在开发模式和生产模式中捆绑和运行不同代码。在开发模式和生产模式中捆绑并运行不同的代码是非常强大的。在开发模式中,React里有许多预警,可以帮助我们在导致bug之前找到问题。然而,检测此类错误所需的代码通常会增加bundle文件的大小,并使应用程序运行得更慢。在开发模式中程序运行缓慢是可以接受的。

    2020/03/26
  • 智通人才网小白攻略_提供网络、现场、校园招聘

    智通人才网小白攻略 官方网址:http://www.job5156.com/ 简介描述:提供网络、现场、校园招聘 智通人才网提供最全最新招聘信息,为企业提供网络招聘、现场招聘会、校…

    2020/03/06
  • randomColor.js指南攻略_js生成随机颜色

    randomColor.js指南攻略 官方网址:https://randomcolor.lllllllllllllllll.com/ GitHub:https://github.c…

    2020/03/06
  • 阿拉丁指数基础教程_微信小程序微信指数排名平台

    阿拉丁指数基础教程 官方网址:http://www.aldzs.com/ 简介描述:微信小程序微信指数排名平台 阿拉丁指数-微信小程序微信指数排名平台,可查询全网小程序排名指数变化…

    2020/03/06
  • IT实用技能小白基础IT开发编程实用技巧_IT使用教程

    1. 上帝的规矩:局部性原理这个原理讲的是在一段时间里, 整个程序的执行仅限于程序的某一个部分, 相应的, 程序访问的存储空间也局限于某一个内存区域, 具体分为:(1) 时间局部性:是指如果程序中的某条指令一旦执行,则不久之后该指令可能再次被执行; 如果某数据被访问,则不久之后该数据可能再次被访问。(2) 空间局部性: 是指一旦程序访问了某个存储单元,则不久

    2020/04/03
  • 程序员如何赚钱使用说明_程序员使用攻略

    作为一个程序员,时常都会想以后自己干不动的时候该怎样办?1. 努力工作每天上班都认认真真,这样就会有好的绩效,年终奖就会多一点。可能公司坑一点的话,年底是没有年终奖的。你不满工资,向上面提出要涨工资。老板看重你的能力,给你涨,一次给你调个1000。可能你这一年就只能调个1000,想要多要点,老板说这是公司制度,每次涨幅是有规定的,给你调1000已经很重视你了

    2020/04/03
  • 小程序获取当前路径和参数小白指南_参数小白攻略

    基本用法获取路径var pages = getCurrentPages(); //获取加载的页面
    var currentPage = pages[pages.length – 1] //获取当前页面的对象
    var url = currentPage.route //获取页面url
    console.log(url); //打印url
    获取路

    2020/03/24
  • 常用的CSS属性小白指南_属性使用帮助

    1,盒模型页面渲染时,dom元素所采用的 布局模型,可以通过 box-sizing 进行设置,根据计算高度的区域可分为:content-box (W3C 标准盒模型)border-box (IE盒模型)1,content-box中,元素的宽,高包含元素的 padding,border// div大小为 140 * 140,内容盒大小为 100 * 100
    d

    2020/03/26
  • 数据库的选择:数据库种类那么多,该如何选择?菜鸟知识_数据库小白攻略

    技术真的是日新月异,Web 网站已经脱离之前的静态网站的体系,转而使用动态语言搭建的动态网站。这也衍生出一个问题:该如何存储数据了?数据库就应运而生,它的作用是提供存储数据的容器。方便 web 网站进行存储、查询、更新等。数据库种类也很多,有成熟且稳定的 MySql 数据库,有后起之秀的 MongoDB 数据库,也有新时代宠儿 Redis 数据库。除此之外,

    2020/04/03
  • 在现代JavaScript中编写异步任务菜鸟知识_异步使用说明

    在本文中,我们将探讨过去围绕异步执行的JavaScript的演变以及它如何改变我们编写和读取代码的方式。我们将从Web开发的开始,一直到现代异步模式示例。JavaScript作为编程语言具有两个主要特征,这两个特征对于理解我们的代码是如何工作的都很重要。首先是它的同步特性,这意味着代码将几乎在您阅读时逐行运行,其次,它是单线程的,任何时候都只执行一个命令。随

    2020/03/20
  • Casper.js教程视频一个基于PhantomJS和SlimerJS的前端端对端测试框架

    Casper.js基础入门 官方网址:http://casperjs.org/ GitHub:https://github.com/casperjs/casperjs 简介描述:一…

    2020/03/05
  • 如何将ES6转换成ES5?小白常识_Babel基础入门

    一、 介绍ECMAScript 6(ES6)的发展速度非常之快,但现代浏览器对ES6新特性支持度不高,所以要想在浏览器中直接使用ES6的新特性就得借助别的工具来实现。Babel是一个广泛使用的转码器,babel可以将ES6代码完美地转换为ES5代码,所以我们不用等到浏览器的支持就可以在项目中使用ES6的特性。二、使用1、新建工程文件夹这里起名叫做es6,然后

    2020/03/23
  • 整理经常在H5移动端开发遇到的知识菜鸟攻略_移动端零基础入门

    viewport、强制浏览器全屏、IOS的Web APP模式、可点击元素出现阴影(这个我觉得真没必要去掉,用户点击是需要反馈的,而这个背景色刚刚好提供了一种反馈)等等,太多啦,这些相信大家百度一下就可以查到很多资料本篇文章主要是讲一些其他的或者优化手段。内容不多1. 弹出数字键盘

    2020/03/23
  • 牛客网入门百科专业IT笔试面试备考平台

    牛客网基础入门 官方网址:https://www.nowcoder.com/ 简介描述:专业IT笔试面试备考平台 牛客网是互联网求职神器,C++、Java、前端、产品、运营技能学习…

    2020/03/05