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

面试热题(三数之和)

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

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

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

输入: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] 。
注意,输出的顺序和三元组的顺序并不重要。

       梦开始的地方(两数之和),这其实和两数之和的做法大同小异,三数之和我们开始将其拆分成一数枚举,剩余两数凑结果即可

        因为我们利用类似于滑动窗口类似的技巧,所以我们必须要求该数组是一个有序的数组,所以我们先要对数组进行排序

 Arrays.sort(nums);

然后对数组中的每个元素进行枚举,相当于确定一个数

 //因为我们这是三数之和,所以我们的第一个数醉倒可以枚举到倒数第三个数for (int i = 0; i < nums.length - 2; i++) {}

因为在遍历的时候,我们可以优先的对过程进行剪枝操作:

1.如果前面3个数相加已经大于零,后面的数就不可能在等于零,故可以剪去

2.如果第一个数加上最大的两个数都小于零,最大的数都小于零,更何况中间的数呢?故可以进行剪去

3.因为题目中不允许我们又重复的结果出现,我们也可以将其进行剪去

那么我们就可以得到如下:

             int x = nums[i];//如果前三个数之和大于零,后面的数之和就不可能有等于零的情况if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {break;}//加上两个最大的值也小于零,直接跳过这个x值if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {continue;}//为了避免重复的情况的发生,如果相等则直接跳过if (i>0&&nums[i] == nums[i - 1]) {continue;}

       现在的问题就转换成在固定的区间内找到满足target的两数之和,通过双指针不断的从两边收缩进行求解

            int j = i + 1;int k = n-1;while (j < k) {//两数和int sum = x + nums[k] + nums[j];//如果大于,说明k指向的数太大了,往左移if (sum > 0) {k--;//如果小于,说明j指向的数太小了,往右移} else if (sum < 0) {j++;//如果相等,先将3个符合条件的数添加到list中去} else {list.add(Arrays.asList(x,nums[j],nums[k]));//为了避免结果重复,左指针碰到相邻重复的直接跳过while (j < k && nums[j] == nums[j+1]) {j++;}j++;// //为了避免结果重复,右指针碰到相邻重复的直接跳过while (j < k && nums[k] == nums[k-1]) {k--;}k--;}}

源码如下:

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> list = new ArrayList<>();//先对入参进行判断,如果nums为空,直接返回if (nums == null || nums.length == 0) {return list;}Arrays.sort(nums);int n = nums.length;//枚举每一个元素,设置两个指针进行跑for (int i = 0; i < nums.length - 2; i++) {int x = nums[i];//如果前三个数之和大于零,后面的数之和就不可能有等于零的情况if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {break;}//加上两个最大的值也小于零,直接跳过这个x值if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {continue;}//为了避免重复的情况的发生,如果相等则直接跳过if (i>0&&nums[i] == nums[i - 1]) {continue;}int j = i + 1;int k = n-1;while (j < k) {int sum = x + nums[k] + nums[j];if (sum > 0) {k--;} else if (sum < 0) {j++;} else {list.add(Arrays.asList(x,nums[j],nums[k]));while (j < k && nums[j] == nums[j+1]) {j++;}j++;while (j < k && nums[k] == nums[k-1]) {k--;}k--;}}}return list;}

相关文章:

面试热题(三数之和)

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

在idea运行python文件

在idea运行python文件 如果在idea运行python文件而没有弹出run的选项&#xff0c;则点击File->Settings…->Plugins&#xff0c;在里面搜索python&#xff0c;如果没有显示则在Maketplace进行搜索&#xff0c; 接着Install&#xff0c;然后restart...

SQL - limit

介绍: limit 是限制的意思, 用于限制返回的查询结果的行数(可以通过limit指定查询多少行数据). MySQL支持limit语法, 用来完成分页. 用法: select 字段1, 字段2, ... from table_name limit offset, length;参数说明: offset: 起始行数, 从0开始计数, 如果省略, 则默认为…...

11. Redis基础知识

文章目录 一、概述二、数据类型STRINGLISTSETHASHZSET 三、数据结构字典跳跃表 四、使用场景计数器缓存查找表消息队列会话缓存分布式锁实现其它 五、Redis 与 Memcached数据类型数据持久化分布式内存管理机制 六、键的过期时间七、数据淘汰策略八、持久化RDB 持久化AOF 持久化…...

list模拟实现【引入反向迭代器】

文章目录 1.适配器1.1传统意义上的适配器1.2语言里的适配器1.3理解 2.list模拟实现【注意看反向迭代器】2.1 list_frame.h2.2riterator.h2.3list.h2.4 vector.h2.5test.cpp 3.反向迭代器的应用1.使用要求2.迭代器的分类 1.适配器 1.1传统意义上的适配器 1.2语言里的适配器 容…...

【华为OD机试】字符串变换最小字符串【2023 B卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述: 给定一个字符串s,最多只能进行一次变换,返回变换后能得到的最小字符串(按照字典序进行比较)。 变换规则:交换字符串中任意两个不同位置的字符。 输入描述: 一串小写字母组成的字…...

ARTS 挑战打卡的第8天 ---volatile 关键字在MCU中的作用,四个实例讲解(Tips)

前言 &#xff08;1&#xff09;volatile 关键字作为嵌入式面试的常考点&#xff0c;很多人都不是很了解&#xff0c;或者说一知半解。 &#xff08;2&#xff09;可能有些人会说了&#xff0c;volatile 关键字不就是防止编译器优化的吗&#xff1f;有啥好详细讲解的&#xff1…...

第二课-一键安装SD-Stable Diffusion 教程

前言 看完这篇文章并跟着操作,就可以在本地开始 SD 绘图了。 理论上来说,这篇课程结束,想要画什么图都可以画了。 启动器介绍 SD 是开源的,可以在 github 上找到。但直接下载源码安装,非常费劲,而且因为国内外差异,就是我这样的秃头程序员也难以应对。 所以,我们改…...

Vue3 动态列 <el-table-column> 实现 formatter 的两种方法

文章目录 动态列实现动态列实现formatter第一种第二种方法 动态列实现 参考此篇文章 Vue3 动态列实现 动态列实现formatter 第一种 以此为例&#xff1a;传递该行的wxUserInfo字段&#xff08;对象&#xff09;中的nickName 假设该行 {prop: "wxUserInfo", label: …...

室温超导是什么?有哪些应用场景?

目录 一、应用场景&#xff1a;二、案例分析&#xff1a; 室温超导是指在室温下&#xff08;即约 20C 至 30C&#xff09;实现超导现象的材料。超导是指某些材料在低温下电阻为零的物理现象&#xff0c;室温超导材料是超导材料的一种。室温超导现象的发现和研究是超导领域的一个…...

Windows+VMware+Ubuntu+Anaconda+VMware Tools

Q1&#xff1a;Windows不支持***agent模拟器 A1&#xff1a;在VMware安装Ubuntu虚拟机 P1: 下载 VMware-workstation-full-15.5.6-16341506.exe 安装包&#xff08;峰哥电脑软件&#xff09; P2: 下载Ubuntu镜像 地址 ubuntu-18.04.6-desktop-amd64.iso P3&#xff1a;搭载镜…...

Xray配置文件详解

Xray配置文件详解 1.并发配置2.HTTP配置3.插件配置4.被动代理配置5.反连平台配置1.并发配置 在配置文件中可以用下面的配置改变漏洞探测的 worker 数量: parallel: 30 # 漏洞探测的 worker 数量,可以简单理解为同时有 30 个 POC 在运行这个值并非越大越好,因为高并发的情况…...

flink优化

1. 大状态调优 大状态调优&#xff1a;在我们的项目中&#xff0c;在做新老访客修复时&#xff0c;我们将每个mid的访问时间都存到了状态里面&#xff0c;在做回流用户数时&#xff0c;我们将每个用户的登录时间都存到了状态里面&#xff0c;导致了大状态问题&#xff0c;由于…...

docker: ERROR: Couldn‘t connect to Docker daemon at http+docker://localhost

环境&#xff1a; linuxt centos 7.x 如下图&#xff0c; 使用docker-compose时&#xff0c;提示错误 [explorebridge tinyproxy]$ docker-compose up ERROR: Couldnt connect to Docker daemon at httpdocker://localhost - is it running?If its at a non-standard locati…...

大模型在金融医疗、生命系统和物理仿真领域的创新应用探索

点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入&#xff01; 在当今迅速发展的科技领域&#xff0c;大模型技术正日益成为金融医疗、生命系统和物理仿真等领域中的重要工具。2023年6月16日&#xff0c;AI TIME举办的青年科学家大模型专场活动邀请了国防科技大学理学院数学…...

tensorflow / tensorflow-gpu cuda cudNN tensorRT 安装,启用显卡加速

tensorflow / tensorflow-gpu cuda cudNN tensorRT 安装,启用显卡加速 说明 Tensorflow-GPU 已被移除。请安装 tensorflow 。 tensorflow 通过 Nvidia CUDA 支持 GPU 加速操作。 自 2019 年 9月发布 的 TensorFlow2.1 以来&#xff0c;tensorFlow 和 tensorflow-GPU 一直是同…...

计算机视觉中的Transformer

几十年来&#xff0c;理论物理学家一直在努力提出一个宏大的统一理论。通过统一&#xff0c;指的是将被认为是完全不同的两个或多个想法结合起来&#xff0c;将它们的不同方面证明为同一基础现象。一个例子是在19世纪之前&#xff0c;电和磁被看作是无关的现象&#xff0c;但电…...

UVA-1601 万圣节后的早晨 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版 以三个点的当前位置作为状态&#xff0c;广度优先遍历&#xff0c;找到终点即为最短次数。 注意&#xff1a; 一次可以移动多个点&#xff0c;但是每个点只能移动一步。在同一次中&#xf…...

nacos 403错误

403错误 2023-08-12 18:04:55,418 [main] ERROR [com.alibaba.cloud.nacos.client.NacosPropertySourceBuilder:106] [trace,span,parent] - get data from Nacos error,dataId:gateway-server.yaml, com.alibaba.nacos.api.exception.NacosException: <html><body&…...

Python遥感图像处理应用篇(三十四):GDAL+Scikit-image+GLCM计算遥感图像纹理特征

1.运行环境 GDAL 3.4.2,Scikit-image最新版本0.19.3,numpy1.21.5 GDAL主要用于实现图像的读取和保存,Scikit-image和numpy对图像进行各种计算处理。 在调试好之前,由于numpy版本(1.16.6)低的问题,运行提示如下错误,更新为1.21.5版本之后就可以正常运行了,在此记录一…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...