当前位置: 首页 > news >正文

百度秋招突击手册面试算法题:三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

提示:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

这是一道百度的一面试题

小编第一次面试就是在这里挂的,回头想想真的有点可惜

那么咱们说一下解题方案

输出:[[-1,-1,2],[-1,0,1]]”这个关键字眼很重要,这个是决定你要返回的值是List<List<Integer>>,是一个嵌套的List集合,而不是单个list,注意这点非常重要,不然你怎么也写不对

List<List<Integer>> ans=new ArrayList<>();


首先对数组进行排序(使用java自带的排序方法来对数组进行排序)

Arrays.sort(nums);

再使用左右指针指向 nums[i]后面的两端,数字分别为 nums[L] 和 nums[R],计算三个数的和 sum判断是否满足为 0,满足则添加进结果集(注意这个过程需要不断去重)

如果 nums[i]大于 000,则三数之和必然无法等于 000,结束循环
如果 nums[i]== nums[i−1],则说明该数字重复,会导致结果重复,所以应该跳过
当 sum == 0 时,nums[L] == nums[L+1] 则会导致结果重复,应该跳过,L++
当 sum == 0 时,nums[R] == nums[R−1] 则会导致结果重复,应该跳过,R−−

 for(int i=0;i<len;i++){if(nums[i]>0){break;}if(i>0&&nums[i]==nums[i-1]){continue;}int L=i+1;int R=len-1;while(L<R){int sum=nums[i]+nums[L]+nums[R];if(sum==0){ans.add(Arrays.asList(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--;}}

最后返回 List<List<Integer>>嵌套数组


完整代码
 

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ans=new ArrayList<>();int len=nums.length;if(nums==null||len<3){return ans;}Arrays.sort(nums);for(int i=0;i<len;i++){if(nums[i]>0){break;}if(i>0&&nums[i]==nums[i-1]){continue;}int L=i+1;int R=len-1;while(L<R){int sum=nums[i]+nums[L]+nums[R];if(sum==0){ans.add(Arrays.asList(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 ans;}
}

声明:该思路以及代码转载自力扣用户:画手大鹏

画手大鹏个人链接:https://leetcode.cn/problems/3sum/

相关文章:

百度秋招突击手册面试算法题:三数之和

给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组。 示例 …...

归并排序 图解 递归 + 非递归 + 笔记

前置知识&#xff1a;讲解019-算法笔试中处理输入和输出&#xff0c;讲解020-递归和master公式 (1)左部分排好序&#xff0c;右部分排好序&#xff0c;利用merge过程让左右整体有序(2)merge过程:谁小拷贝谁&#xff0c;直到左右两部分所有的数字耗尽(3)递归实现和非递归实现(4…...

2023 年最好的 Android 系统修复/刷机应用程序和软件

任何 Android 设备要顺利运行&#xff0c;其操作系统必须运行良好。幸运的是&#xff0c;对于大多数 Android 用户来说&#xff0c;这是不间断的。设备运行良好&#xff0c;打电话、共享文档等都没有问题。尽管如此&#xff0c;Android 操作系统可能会停止运行。这可能是由于特…...

Linux下内网穿透实现云原生观测分析工具的远程访问

&#x1f4d1;前言 本文主要是Linux下内网穿透实现云原生观测分析工具的远程访问设置的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是青衿&#x1f947; ☁️博客首页&#xff1a;CSDN主页放风讲故事 &…...

卡数据兼容性要求-M2M架构

EUM 应在生产 eUICC 过程中安装并初始化 ISD-R. eUICC 出厂后&#xff0c; ISD-R 应进入 GlobalPlatform Card Specification [GP CS]第 5.3 节中定义的生命周期状态 "PERSONALIZED". ISD-R 权力授予应遵循[GS RPT]附录 C 中的定义. EUM 应在 eUICC 生产过程中安装并…...

C++入门篇3(类和对象【重点】)

文章目录 C入门篇3&#xff08;类和对象【重点】&#xff09;1、面向过程和面向对象2、类的引入3、类的定义4、类的访问限定符及封装4.1、访问限定符4.2、封装 5、类的作用域6、类的实例化&#xff08;对象&#xff09;7、类对象模型7.1、类对象的存储方式7.2、结构体&#xff…...

【开源】基于Vue.js的生活废品回收系统的设计和实现

目录 一、摘要1.1 项目介绍1.2 项目详细录屏 二、研究内容三、界面展示3.1 登录注册3.2 资源类型&资源品类模块3.3 回收机构模块3.4 资源求购/出售/交易单模块3.5 客服咨询模块 四、免责说明 一、摘要 1.1 项目介绍 生活废品回收系统是可持续发展的解决方案&#xff0c;旨…...

Mysql配置主从复制-GTID模式

目录 主从复制 主从复制的定义 主从复制的原理 主从复制的优势 主从复制的形式 主从复制的模式 主从复制的类型 GTID模式 GTID的概念 GTID的优势 GTID的原理 GTID的配置 Mysql主服务器 ​编辑 Mysql从服务器 ​编辑 主从复制 主从复制的定义 是指把数据从一个…...

Flink之状态管理

Flink状态管理 状态概述状态分类 键控、按键分区状态概述值状态 ValueState列表状态 ListStateMap状态 MapState归约状态 ReducingState聚合状态 Aggregating State 算子状态概述列表状态 ListState联合列表状态 UnionListState广播状态 Broadcast State 状态有效期 (TTL)概述S…...

[Mac软件]Adobe Media Encoder 2024 V24.0.2免激活版

软件说明 使用Media Encoder&#xff0c;您将能够处理和管理多媒体。插入、转码、创建代理版本&#xff0c;并几乎以任何可用的格式输出。在应用程序中以单一方式使用多媒体&#xff0c;包括Premiere Pro、After Effects和Audition。 紧密整合 与Adobe Premiere Pro、After …...

Bytebase 2.11.0 - 支持 OceanBase Oracle 模式

&#x1f680; 新功能 支持 OceanBase Oracle 模式。支持设置 MySQL 在线变更参数。新增项目数据库查看者的角色。 &#x1f384; 改进 支持在项目中直接选择所有用户并为之添加角色。 调整了项目页面的布局。在 SQL 编辑器中通过悬浮面板展示表和列的详情。 &#x1faa6; …...

『CV学习笔记』文本识别算法CRNNSVTR介绍

文本识别算法CRNN&SVTR介绍 文章目录 一. 文本识别1.1. 文本识别方法介绍1.1.1. 规则文本识别1.1.2. 不规则文本识别1.2. CRNN算法原理1.2.1. CRNN基本网络结构1.3. SVTR算法原理二. 参考文献一. 文本识别 文本识别是OCR(Optical Character Recognition)的一个子任务,其…...

HaaS510开板式DTU真机连云:上报监测数据至阿里云物联网平台

背景 HaaS: Hardware as a Service。 HAAS510 是一种开板式 DTU &#xff0c;旨在为用户已开发好的设备快速增加 4G 连云能力的 4G CAT1 数传模块。它通过将模组与用户设备集成到一个外壳内&#xff0c;既保持设备的一体性&#xff0c;又降低重新开发 PCB 的时间消耗和模组开…...

贾扬清开源 AI 框架 Caffe | 开源英雄

【编者按】在开源与人工智能的灿烂星河里&#xff0c;贾扬清的名字都格外地耀眼。因为导师 Trevor Darrell 教授的一句“你是想多花时间写一篇大家估计不是很在意的毕业论文&#xff0c;还是写一个将来大家都会用的框架&#xff1f;”&#xff0c;学生贾扬清一头扎进了创 Caffe…...

【objectarx.net】使用公式自动更新表格项的内容

使用公式自动更新表格项的内容...

CSS 移动端 1px(线条/边框) 不同机型上显示粗细不同,解决办法

由于不同的手机有不同的像素密度导致的。如果移动显示屏的分辨率始终是普通屏幕的2倍&#xff0c;1px的边框在devicePixelRatio2的移动显示屏下会显示成2px&#xff0c;所以在高清瓶下看着1px总是感觉变胖了 <!DOCTYPE html> <html lang"en"> <head&g…...

vue3使用vuex的示例(模块化功能)

目录 1. store/index.ts 2. main.ts 3. App.vue调用 4. 如果删除moduleA的namespaced属性, 保留moduleB的namespaced:true 5. 则App.vue修改为: 1. store/index.ts 注意: 需要使用时带上模块名称的namespaced必须为true, 不写或者为false时调用时不需要写模块名称(获取st…...

Vatee万腾的科技决策力奇迹:Vatee科技决策力的独特之选

在金融投资的复杂领域中&#xff0c;Vatee万腾以其独特的科技决策力创造了一场真正的奇迹。这不仅是一种引领投资者走向成功的选择&#xff0c;更是一种开启新时代的科技决策奇迹。 Vatee的科技决策力背后蕴藏着强大的智慧和创新。通过大数据分析、智能算法的运用&#xff0c;V…...

ai技术是怎么换脸的,实现原理是什么,有那些软件

人工智能&#xff08;AI&#xff09;在近年来的迅猛发展中&#xff0c;带来了许多令人惊叹的技术创新&#xff0c;其中之一就是人工智能换脸技术。这项技术通过深度学习和图像处理的手段&#xff0c;使得用户可以将自己的面孔替换成其他人物&#xff0c;引发了广泛的讨论和应用…...

在IDEA中使用maven项目总结

一 什么是maven Maven本身也是Java写的&#xff0c;他是一款服务于Java平台的自动化构建工具 Maven是一个项目管理工具&#xff0c;旨在简化软件项目的构建、依赖管理和项目信息管理。它使用基于项目对象模型&#xff08;Project Object Model&#xff0c;POM&#xff09;的…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

break 语句和 continue 语句

break语句和continue语句都具有跳转作用&#xff0c;可以让代码不按既有的顺序执行 break break语句用于跳出代码块或循环 1 2 3 4 5 6 for (var i 0; i < 5; i) { if (i 3){ break; } console.log(i); } continue continue语句用于立即终…...

使用 uv 工具快速部署并管理 vLLM 推理环境

uv&#xff1a;现代 Python 项目管理的高效助手 uv&#xff1a;Rust 驱动的 Python 包管理新时代 在部署大语言模型&#xff08;LLM&#xff09;推理服务时&#xff0c;vLLM 是一个备受关注的方案&#xff0c;具备高吞吐、低延迟和对 OpenAI API 的良好兼容性。为了提高部署效…...