百度秋招突击手册面试算法题:三数之和
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != 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 ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例 …...
归并排序 图解 递归 + 非递归 + 笔记
前置知识:讲解019-算法笔试中处理输入和输出,讲解020-递归和master公式 (1)左部分排好序,右部分排好序,利用merge过程让左右整体有序(2)merge过程:谁小拷贝谁,直到左右两部分所有的数字耗尽(3)递归实现和非递归实现(4…...
2023 年最好的 Android 系统修复/刷机应用程序和软件
任何 Android 设备要顺利运行,其操作系统必须运行良好。幸运的是,对于大多数 Android 用户来说,这是不间断的。设备运行良好,打电话、共享文档等都没有问题。尽管如此,Android 操作系统可能会停止运行。这可能是由于特…...
Linux下内网穿透实现云原生观测分析工具的远程访问
📑前言 本文主要是Linux下内网穿透实现云原生观测分析工具的远程访问设置的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是青衿🥇 ☁️博客首页:CSDN主页放风讲故事 &…...
卡数据兼容性要求-M2M架构
EUM 应在生产 eUICC 过程中安装并初始化 ISD-R. eUICC 出厂后, ISD-R 应进入 GlobalPlatform Card Specification [GP CS]第 5.3 节中定义的生命周期状态 "PERSONALIZED". ISD-R 权力授予应遵循[GS RPT]附录 C 中的定义. EUM 应在 eUICC 生产过程中安装并…...
C++入门篇3(类和对象【重点】)
文章目录 C入门篇3(类和对象【重点】)1、面向过程和面向对象2、类的引入3、类的定义4、类的访问限定符及封装4.1、访问限定符4.2、封装 5、类的作用域6、类的实例化(对象)7、类对象模型7.1、类对象的存储方式7.2、结构体ÿ…...
【开源】基于Vue.js的生活废品回收系统的设计和实现
目录 一、摘要1.1 项目介绍1.2 项目详细录屏 二、研究内容三、界面展示3.1 登录注册3.2 资源类型&资源品类模块3.3 回收机构模块3.4 资源求购/出售/交易单模块3.5 客服咨询模块 四、免责说明 一、摘要 1.1 项目介绍 生活废品回收系统是可持续发展的解决方案,旨…...
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,您将能够处理和管理多媒体。插入、转码、创建代理版本,并几乎以任何可用的格式输出。在应用程序中以单一方式使用多媒体,包括Premiere Pro、After Effects和Audition。 紧密整合 与Adobe Premiere Pro、After …...
Bytebase 2.11.0 - 支持 OceanBase Oracle 模式
🚀 新功能 支持 OceanBase Oracle 模式。支持设置 MySQL 在线变更参数。新增项目数据库查看者的角色。 🎄 改进 支持在项目中直接选择所有用户并为之添加角色。 调整了项目页面的布局。在 SQL 编辑器中通过悬浮面板展示表和列的详情。 🪦 …...
『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 ,旨在为用户已开发好的设备快速增加 4G 连云能力的 4G CAT1 数传模块。它通过将模组与用户设备集成到一个外壳内,既保持设备的一体性,又降低重新开发 PCB 的时间消耗和模组开…...
贾扬清开源 AI 框架 Caffe | 开源英雄
【编者按】在开源与人工智能的灿烂星河里,贾扬清的名字都格外地耀眼。因为导师 Trevor Darrell 教授的一句“你是想多花时间写一篇大家估计不是很在意的毕业论文,还是写一个将来大家都会用的框架?”,学生贾扬清一头扎进了创 Caffe…...
【objectarx.net】使用公式自动更新表格项的内容
使用公式自动更新表格项的内容...
CSS 移动端 1px(线条/边框) 不同机型上显示粗细不同,解决办法
由于不同的手机有不同的像素密度导致的。如果移动显示屏的分辨率始终是普通屏幕的2倍,1px的边框在devicePixelRatio2的移动显示屏下会显示成2px,所以在高清瓶下看着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科技决策力的独特之选
在金融投资的复杂领域中,Vatee万腾以其独特的科技决策力创造了一场真正的奇迹。这不仅是一种引领投资者走向成功的选择,更是一种开启新时代的科技决策奇迹。 Vatee的科技决策力背后蕴藏着强大的智慧和创新。通过大数据分析、智能算法的运用,V…...
ai技术是怎么换脸的,实现原理是什么,有那些软件
人工智能(AI)在近年来的迅猛发展中,带来了许多令人惊叹的技术创新,其中之一就是人工智能换脸技术。这项技术通过深度学习和图像处理的手段,使得用户可以将自己的面孔替换成其他人物,引发了广泛的讨论和应用…...
在IDEA中使用maven项目总结
一 什么是maven Maven本身也是Java写的,他是一款服务于Java平台的自动化构建工具 Maven是一个项目管理工具,旨在简化软件项目的构建、依赖管理和项目信息管理。它使用基于项目对象模型(Project Object Model,POM)的…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...
STM32标准库-ADC数模转换器
文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”:输入模块(GPIO、温度、V_REFINT)1.4.2 信号 “调度站”:多路开关1.4.3 信号 “加工厂”:ADC 转换器(规则组 注入…...
算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
