【算法】梦破碎之地---三数之和
相信大家都有做过两数之和,
题目链接: 15. 三数之和 - 力扣(LeetCode)
在文章的开始让我们回顾一下三数之和吧!
题目描述:
给你一个整数数组 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 。
解题思路:
首先要使形如a + b +c = 0,我们可以座一层循环,让i表示a,通过双指针表示另外两个数,left-->b,right-->c;在动手解题前一定要对数组做预处理,排序,这样可以避免很多麻烦,我们让i从数组下标第一个元素开始,left取i + 1;right取nums.length - 1;i不动,让两个指针移动,判断sum=a+b+c的值,当sum>0时,证明整体大了需要减小和,故使right--;当sum<0时,证明整体小了需要增大和,故使left++;sum=0即一组解。
整体思路就是这样,当其实有很多细节的地方,尤其是 去重,这也是解本题最关键的地方,我们需要对a b c去重,避免重复解。
对a去重: if(i>0 and nums[i]==nums[i-1]) continue;
对b c去重: if(right > left and nums[right] = nums[right--] ) right--;
if (right > left and nums[left] = nums[left++] ) left++;
上代码:
代码详解可看(强推,简单易懂,细节拉满): 梦破碎的地方!| LeetCode:15.三数之和_哔哩哔哩_bilibili
class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();//预处理---》排序Arrays.sort(nums);for(int i=0;i < nums.length;i++){if(nums[i] > 0) break; // 对a去重if(i > 0 && nums[i] == nums[i - 1]){continue;}int left = i + 1;int right = nums.length - 1;// 指针移动条件while(right > left){int sum = nums[i] + nums[left] + nums[right];if(sum > 0){right--;}else if(sum < 0){left++;}else{// 先收获结果集在去重 确保至少收获一个结果集res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 对b c去重 这里需要移动 不能用if做判断会漏解的****while(right > left && nums[left] == nums[left+1]){left++;}while(right > left && nums[right] == nums[right-1]){right--;}right--;left++;}}}return res;}
}
这里在给出一个版本的参考:
如果有朋友实在理解不了的话这里给出一个n数之和的解决方案,直接就是背
c++版本:
class Solution {public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());// n 为 3,从 nums[0] 开始计算和为 0 的三元组return nSumTarget(nums, 3, 0, 0);}/* 注意:调用这个函数之前一定要先给 nums 排序 */// n 填写想求的是几数之和,start 从哪个索引开始计算(一般填 0),target 填想凑出的目标和vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target) {int sz = nums.size();vector<vector<int>> res;// 至少是 2Sum,且数组大小不应该小于 nif (n < 2 || sz < n) return res;// 2Sum 是 base caseif (n == 2) {// 双指针那一套操作int lo = start, hi = sz - 1;while (lo < hi) {int sum = nums[lo] + nums[hi];int left = nums[lo], right = nums[hi];if (sum < target) {while (lo < hi && nums[lo] == left) lo++;} else if (sum > target) {while (lo < hi && nums[hi] == right) hi--;} else {res.push_back({left, right});while (lo < hi && nums[lo] == left) lo++;while (lo < hi && nums[hi] == right) hi--;}}} else {// n > 2 时,递归计算 (n-1)Sum 的结果for (int i = start; i < sz; i++) {vector<vector<int>>sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);for (vector<int>& arr : sub) {// (n-1)Sum 加上 nums[i] 就是 nSumarr.push_back(nums[i]);res.push_back(arr);}while (i < sz - 1 && nums[i] == nums[i + 1]) i++;}}return res;}
};
java版本:
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);// n 为 3,从 nums[0] 开始计算和为 0 的三元组return nSumTarget(nums, 3, 0, 0);}/* 注意:调用这个函数之前一定要先给 nums 排序 */// n 填写想求的是几数之和,start 从哪个索引开始计算(一般填 0),target 填想凑出的目标和public List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target) {int sz = nums.length;List<List<Integer>> res = new ArrayList<>();// 至少是 2Sum,且数组大小不应该小于 nif (n < 2 || sz < n) return res;// 2Sum 是 base caseif (n == 2) {// 双指针那一套操作int lo = start, hi = sz - 1;while (lo < hi) {int sum = nums[lo] + nums[hi];int left = nums[lo], right = nums[hi];if (sum < target) {while (lo < hi && nums[lo] == left) lo++;} else if (sum > target) {while (lo < hi && nums[hi] == right) hi--;} else {res.add(new ArrayList<>(Arrays.asList(left, right)));while (lo < hi && nums[lo] == left) lo++;while (lo < hi && nums[hi] == right) hi--;}}} else {// n > 2 时,递归计算 (n-1)Sum 的结果for (int i = start; i < sz; i++) {List<List<Integer>>sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);for (List<Integer> arr : sub) {// (n-1)Sum 加上 nums[i] 就是 nSumarr.add(nums[i]);res.add(arr);}while (i < sz - 1 && nums[i] == nums[i + 1]) i++;}}return res;}
}
相关文章:
【算法】梦破碎之地---三数之和
相信大家都有做过两数之和, 题目链接: 15. 三数之和 - 力扣(LeetCode) 在文章的开始让我们回顾一下三数之和吧! 题目描述: 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], …...
c语言如何将一个文本内容复制到另外一个文本里
c语言如果要把一个文本文件的文件复制到另外一个文件里,代码如下 #include<stdio.h>int main() {FILE *fp1,*fp2;char a;fp1fopen("D://cyy//aaa.txt","r");fp2fopen("ccc.cpu","w");while(a!EOF){afgetc(fp1);fput…...
JavaScript基础(九)
冒泡排序 用例子比较好理解: var arry[7,2,6,3,4,1,8]; //拿出第一位数7和后面依次比较,遇到大的8就换位,8再与后面依次比较,没有能和8换位的数,再从下一位2依次与下面的数比较。 console.log(排列之前:arry); for (…...
决策树最优属性选择
本文以西瓜数据集为例演示决策树使用信息增益选择最优划分属性的过程 西瓜数据集下载:传送门 首先计算根节点的信息熵: 数据集分为好瓜、坏瓜,所以|y|2根结点包含17个训练样例,其中好瓜共计8个样例,所占比例为8/17坏…...
NER 数据集格式转换
NER 数据集格式 格式一 某些地方的数据和标签拆成两个文件了 sentences.txt 如 何 解 决 足 球 界 长 期 存 在 的 诸 多 矛 盾 , 重 振 昔 日 津 门 足 球 的 雄 风 , 成 为 天 津 足 坛 上 下 内 外 到 处 议 论 的 话 题 。 该 县 一 手 抓 农 业…...
【LinuxC语言】utime函数
文章目录 前言函数原型参数`struct utimbuf`返回值示例代码总结前言 utime函数在C语言中用于更改文件的访问时间(access time, atime)和修改时间(modification time, mtime)。这是一个POSIX标准的函数,常用于更新文件的时间戳,而不必实际修改文件的内容。 函数原型 #in…...
Cannot invoke an object which is possibly ‘undefined‘
这是ts中的错误提示: Cannot invoke an object which is possibly undefined 报错场景: 定义interface接口的时候sayHi方法使用的是可选属性,可以有可以没有, 当在实际方法中调用sayHi方法的时候报错了, 问ÿ…...
C++ 计时器
文章目录 一、简介二、实现代码2.1 windows平台2.2 C标准库 三、实现效果 一、简介 有时候总是会用到一些计时的操作,这里也整理了一些代码,包括C标准库以及window自带的时间计算函数。 二、实现代码 2.1 windows平台 StopWatch.h #ifndef STOP_WATCH_H…...
notepad++ 批量转所有文件编码格式为UTF-8
1、安装notepad及PythonScript_3.0.18.0插件 建议两者都保持默认路径安装x64版本: 阿里云盘分享https://www.alipan.com/s/xVUDpY8v5QL安装好后如下图: 2、new Script,新建脚本,文件名为ConvertEncoding 3、自动打开脚本ÿ…...
正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-16讲 EPIT定时器
前言: 本文是根据哔哩哔哩网站上“正点原子[第二期]Linux之ARM(MX6U)裸机篇”视频的学习笔记,在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。…...
【只会for循环? 来看下, Nodejs中典型的5种循环方式】
Nodejs中的,除了经典的for循环 , 其实还有几种好用的循环方式, 并有典型的使用场景。下面来一起看下👇🏻 5种循环用法 For Loop:这是最常见的循环方式,适用于你知道循环次数的情况。 for (let i 0; i &…...
Java基础(三)- 多线程、网络通信、单元测试、反射、注解、动态代理
多线程基础 线程:一个程序内部的一条执行流程,只有一条执行流程就是单线程 java.lang.Thread代表线程 主线程退出,子线程存在,进程不会退出 可以使用jconsole查看 创建线程 有多个方法可以创建线程 继承Thread类 优点&#x…...
WordPress建站公司模板免费下载
WordPress建站公司 适合提供WordPress建站服务的公司或个体(个人)工作室使用的WordPress建站公司主题模板。 演示 https://www.jianzhanpress.com/?p545 https://www.wpicu.com/jianzhan/ 下载 链接: https://pan.baidu.com/s/11trlwUJq_lW81R_acq4ilA 提取码: r19i...
金融信贷风控基础知识
一、所谓风控(What && Why) 所谓风控,可以拆解从2个方面看,即 风险和控制 风险(what) 风险 这里狭隘的特指互联网产品中存在的风险点,例如 账户风险 垃圾注册账号账号被泄露盗用 交易支付风险 刷单:为提升卖家店铺人气…...
Web Server项目实战4-服务器编程基本框架和2种高效的事件处理模式
服务器编程基本框架 虽然服务器程序种类繁多,但其基本框架都一样,不同之处在于逻辑处理 模块功能I/O处理单元处理客户连接,读写网络数据逻辑单元业务进程或线程网络存储单元数据库、文件或缓存请求队列各单元之间的通信方式 I/O 处理单元是…...
。。。。。
...
RPC原理技术
RPC原理技术 背景介绍起源组件实现工作原理 背景 本文内容大多基于网上其他参考文章及资料整理后所得,并非原创,目的是为了需要时方便查看。 介绍 RPC,Remote Procedure Call,远程过程调用,允许像调用本地方法一样调…...
开源大模型与闭源大模型:技术哲学的较量
目录 前言一、 开源大模型的优势1. 社区支持与合作1.1 全球协作网络1.2 快速迭代与创新1.3 共享最佳实践 2. 透明性与可信赖性2.1 审计与验证2.2 减少偏见与错误2.3 安全性提升 3. 低成本与易访问性3.1 降低研发成本3.2 易于定制化3.3 教育资源丰富 4. 促进标准化5. 推动技术进…...
buuctf的RSA(二)
1.RSA 知道 flag.enc 和 pub.key,典型的加密、解密 将pub,key 改为pub.txt 打开后发现公钥 在RSA公私钥分解 Exponent、Modulus,Rsa公私钥指数、系数(模数)分解--查错网 进行解密 得到e65537 n8693448229604811919066606200349480058890565…...
idm软件是做什么的 IDM是啥软件 idm软件怎么下载 idm软件怎么下载
一、IDM是啥软件 IDM 是由美国 Tonec 公司开发的 Windows 软件,该软件最初于 2005 年发布。IDM全称Internet Download Manager,是一款Windows平台老牌而功能强大的下载加速器,专注于互联网数据下载。这款软件是一款不错的轻量级下载工具&…...
STM32CubeIDE实战指南:从代码编译到一键下载的完整流程解析
1. STM32CubeIDE开发环境概述 对于刚接触STM32开发的工程师来说,选择一款合适的集成开发环境(IDE)至关重要。STM32CubeIDE是ST官方推出的免费开发工具,它集成了代码编辑、编译、调试和下载功能于一体,特别适合新手快速上手。我在实际项目中使…...
深度解析Scarab:空洞骑士模组管理器的专业实现与架构设计
深度解析Scarab:空洞骑士模组管理器的专业实现与架构设计 【免费下载链接】Scarab An installer for Hollow Knight mods written with Avalonia. 项目地址: https://gitcode.com/gh_mirrors/sc/Scarab 空洞骑士模组管理器Scarab为玩家提供了高效、专业的模组…...
解密VideoDownloadHelper:开源浏览器插件的智能视频提取技术
解密VideoDownloadHelper:开源浏览器插件的智能视频提取技术 【免费下载链接】VideoDownloadHelper Chrome Extension to Help Download Video for Some Video Sites. 项目地址: https://gitcode.com/gh_mirrors/vi/VideoDownloadHelper 当你在浏览微博、秒拍…...
乌尔都语语音合成落地难?揭秘ElevenLabs未公开的ur-PK语言代码陷阱与ISO 639-3双标适配规范(仅限首批127家认证开发者知晓)
更多请点击: https://intelliparadigm.com 第一章:乌尔都语语音合成落地难?揭秘ElevenLabs未公开的ur-PK语言代码陷阱与ISO 639-3双标适配规范(仅限首批127家认证开发者知晓) ElevenLabs 官方文档中仅标注 ur 为乌尔…...
基于Helm Chart的JupyterHub生产级部署与运维实战指南
1. 项目概述:为什么我们需要一个可扩展的JupyterHub部署方案?如果你在团队里负责过数据科学或机器学习平台的搭建,大概率会为Jupyter Notebook的部署和管理头疼过。单个Jupyter Notebook服务给一两个人用还行,一旦团队规模扩大到十…...
Kubernetes部署Valheim游戏服务器:云原生技术赋能游戏运维实践
1. 项目概述:当维京英灵殿遇上容器编排如果你和我一样,既沉迷于《英灵神殿》(Valheim)里与好友共建家园、挑战上古巨兽的乐趣,又恰好是一名整天和Kubernetes(k8s)打交道的开发者或运维ÿ…...
Pandrator:基于Python的自动化内容生成与数据转换工具实践
1. 项目概述与核心价值最近在折腾一些自动化数据处理和内容生成的工作流,发现了一个挺有意思的开源项目,叫Pandrator。乍一看这个名字,可能会联想到“潘多拉”和“生成器”的结合,实际上它也确实是一个功能强大的内容转换与生成工…...
RTKLIB 2.4.3项目在Visual Studio 2019中的工程化配置:告别零散文件,打造清晰结构
RTKLIB 2.4.3项目在Visual Studio 2019中的工程化配置:告别零散文件,打造清晰结构 对于卫星导航领域的开发者而言,RTKLIB无疑是一个绕不开的开源项目。这个由日本学者Tomoji Takasu开发的GNSS定位软件,以其强大的功能和开放的架构…...
初创团队如何利用Token Plan套餐有效控制AI开发成本
🚀 告别海外账号与网络限制!稳定直连全球优质大模型,限时半价接入中。 👉 点击领取海量免费额度 初创团队如何利用Token Plan套餐有效控制AI开发成本 对于资源有限的初创团队和独立开发者而言,在原型开发和产品验证阶…...
基于Kubernetes跑通第一个云原生应用【20260516】002篇
文章目录 📖 理论深潜:Kubernetes 架构与容器底层原理 1. 云原生与 K8s 核心概念 为什么需要 K8s?(从痛点出发) 深度解析:容器底层三大魔法 ① NameSpace(命名空间):隔离的围墙 ② Cgroups(控制组):资源的天花板 ③ UnionFS(联合文件系统):分层的积木 2. K8s 架…...
