面试热题(三数之和)
给你一个整数数组
nums,判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != 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 ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可以包含重复的三元组。 输入&…...
在idea运行python文件
在idea运行python文件 如果在idea运行python文件而没有弹出run的选项,则点击File->Settings…->Plugins,在里面搜索python,如果没有显示则在Maketplace进行搜索, 接着Install,然后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)
前言 (1)volatile 关键字作为嵌入式面试的常考点,很多人都不是很了解,或者说一知半解。 (2)可能有些人会说了,volatile 关键字不就是防止编译器优化的吗?有啥好详细讲解的࿱…...
第二课-一键安装SD-Stable Diffusion 教程
前言 看完这篇文章并跟着操作,就可以在本地开始 SD 绘图了。 理论上来说,这篇课程结束,想要画什么图都可以画了。 启动器介绍 SD 是开源的,可以在 github 上找到。但直接下载源码安装,非常费劲,而且因为国内外差异,就是我这样的秃头程序员也难以应对。 所以,我们改…...
Vue3 动态列 <el-table-column> 实现 formatter 的两种方法
文章目录 动态列实现动态列实现formatter第一种第二种方法 动态列实现 参考此篇文章 Vue3 动态列实现 动态列实现formatter 第一种 以此为例:传递该行的wxUserInfo字段(对象)中的nickName 假设该行 {prop: "wxUserInfo", label: …...
室温超导是什么?有哪些应用场景?
目录 一、应用场景:二、案例分析: 室温超导是指在室温下(即约 20C 至 30C)实现超导现象的材料。超导是指某些材料在低温下电阻为零的物理现象,室温超导材料是超导材料的一种。室温超导现象的发现和研究是超导领域的一个…...
Windows+VMware+Ubuntu+Anaconda+VMware Tools
Q1:Windows不支持***agent模拟器 A1:在VMware安装Ubuntu虚拟机 P1: 下载 VMware-workstation-full-15.5.6-16341506.exe 安装包(峰哥电脑软件) P2: 下载Ubuntu镜像 地址 ubuntu-18.04.6-desktop-amd64.iso P3:搭载镜…...
Xray配置文件详解
Xray配置文件详解 1.并发配置2.HTTP配置3.插件配置4.被动代理配置5.反连平台配置1.并发配置 在配置文件中可以用下面的配置改变漏洞探测的 worker 数量: parallel: 30 # 漏洞探测的 worker 数量,可以简单理解为同时有 30 个 POC 在运行这个值并非越大越好,因为高并发的情况…...
flink优化
1. 大状态调优 大状态调优:在我们的项目中,在做新老访客修复时,我们将每个mid的访问时间都存到了状态里面,在做回流用户数时,我们将每个用户的登录时间都存到了状态里面,导致了大状态问题,由于…...
docker: ERROR: Couldn‘t connect to Docker daemon at http+docker://localhost
环境: linuxt centos 7.x 如下图, 使用docker-compose时,提示错误 [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爱好者的加入! 在当今迅速发展的科技领域,大模型技术正日益成为金融医疗、生命系统和物理仿真等领域中的重要工具。2023年6月16日,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 以来,tensorFlow 和 tensorflow-GPU 一直是同…...
计算机视觉中的Transformer
几十年来,理论物理学家一直在努力提出一个宏大的统一理论。通过统一,指的是将被认为是完全不同的两个或多个想法结合起来,将它们的不同方面证明为同一基础现象。一个例子是在19世纪之前,电和磁被看作是无关的现象,但电…...
UVA-1601 万圣节后的早晨 题解答案代码 算法竞赛入门经典第二版
GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版 以三个点的当前位置作为状态,广度优先遍历,找到终点即为最短次数。 注意: 一次可以移动多个点,但是每个点只能移动一步。在同一次中…...
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版本之后就可以正常运行了,在此记录一…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
