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

面试经典150题——三数之和

面试经典150题 day29

      • 题目来源
      • 我的题解
        • 方法一 暴力解法 超时
        • 方法二 扩展两数之和(双指针)
        • 方法三 扩展为通用的n数之和

题目来源

力扣每日一题;题序:15

我的题解

方法一 暴力解法 超时

进行三重循环遍历,判断和是否为0,若为0,则将对应的值组合成List并加入Set。

时间复杂度:O( n 3 n^3 n3)
空间复杂度:O(n)

public List<List<Integer>> threeSum(int[] nums) {Set<List<Integer>> resSet=new HashSet<>();int n=nums.length;for(int i=0;i<n-2;i++){for(int j=i+1;j<n-1;j++){for(int k=j+1;k<n;k++){if(nums[i]+nums[j]+nums[k]==0){List<Integer> t=Arrays.asList(nums[i],nums[j],nums[k]);t.sort((a,b)->a-b);resSet.add(t);}}}}return new ArrayList<>(resSet);
}
方法二 扩展两数之和(双指针)

先确定一个数,然后使用两数之和的解法进行计算。注意需要去重,即在求两数之和的过程中需要将去掉重复的元素。

时间复杂度:O( n 2 n^2 n2)。
空间复杂度:O(n)

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res=new ArrayList<>();for(int i=0;i<nums.length;){List<List<Integer>> t=twoSum(nums,-nums[i],i);int pre=nums[i];while(i<nums.length&&nums[i]==pre)i++;res.addAll(t);}return res;
}
public List<List<Integer>> twoSum(int[] nums,int  target,int index){int left=index+1,right=nums.length-1;List<List<Integer>> res=new ArrayList<>();while(left<right){int tNum=nums[left]+nums[right];int preLeft=nums[left];int preRight=nums[right];if(index==left){left++;continue;}if(index==right){right--;continue;}if(tNum==target){List<Integer> t=Arrays.asList(-target,nums[left],nums[right]);res.add(t);while(left<right&&nums[left]==preLeft)left++;while(right>left&&nums[right]==preRight)right--;}else if(tNum<target){while(left<right&&nums[left]==preLeft)left++;}else{while(right>left&&nums[right]==preRight)right--;}}return res;
}
方法三 扩展为通用的n数之和

时间复杂度:O( n 2 n^2 n2)。
空间复杂度:O(n)

public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> resList = nSum(nums, 0, 3, 0);return resList;
}public  List<List<Integer>> nSum(int[] nums, int target, int n, int start) {int len = nums.length;List<List<Integer>> res = new ArrayList<>();if (n == 2) {int left = start, right = len - 1;while (left < right) {int temp = nums[left] + nums[right];int l = nums[left], r = nums[right];if (temp < target) {while (left < right && l == nums[left])left++;} else if (temp > target) {while (left < right && r == nums[right])right--;} else {List<Integer> sub = new ArrayList(Arrays.asList(nums[left], nums[right]));res.add(sub);while (left < right && l == nums[left])left++;while (left < right && r == nums[right])right--;}}} else {for (int i = start; i < len; i++) {List<List<Integer>> subList = nSum(nums, target - nums[i], n - 1, i + 1);for (List<Integer> list : subList) {list.add(nums[i]);res.add(list);}while (i < len - 1 && nums[i] == nums[i + 1])i++;}}return res;
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

相关文章:

面试经典150题——三数之和

面试经典150题 day29 题目来源我的题解方法一 暴力解法 超时方法二 扩展两数之和&#xff08;双指针&#xff09;方法三 扩展为通用的n数之和 题目来源 力扣每日一题&#xff1b;题序&#xff1a;15 我的题解 方法一 暴力解法 超时 进行三重循环遍历&#xff0c;判断和是否为…...

go动态创建/增加channel并处理数据

背景描述 有一个需求&#xff0c;大概可以描述为&#xff1a;有多个websocket连接&#xff0c;因此消息会并发地发送过来&#xff0c;这些消息中有一个标志可以表明是哪个连接发来的消息&#xff0c;但只有收到消息后才能建立channel或写入已有channel&#xff0c;在收消息前无…...

asp.net成绩查询系统

说明文档 运行前附加数据库.mdf&#xff08;或sql生成数据库&#xff09; 主要技术&#xff1a; 基于asp.net架构和sql server数据库 功能模块&#xff1a; asp.net成绩查询系统 学生功能有查看成绩和修改账号密码等 后台管理员可以进行用户管理 管理员添加管理员查询注…...

Express路由

什么是路由 官方定义&#xff1a;路由确定了应用程序如何响应客户端对特定端点的请求。 路由的使用 一个路由的组成有 请求方法、路径 和 回调函数 组成。 Express中提供了一些列方法&#xff0c;可以很方便的使用路由&#xff0c;使用格式如下&#xff1a; app.<metho…...

在做题中学习(53): 寻找旋转数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣&#xff08;LeetCode&#xff09; 解法&#xff1a;O(logn)->很可能就是二分查找 思路&#xff1a;再看看题目要求&#xff0c;可以画出旋转之后数组中元素的大小关系&#xff1a; 首先&#xff0c;数组是具有二段性的(适配二分查…...

C#语言进阶(三) 元组

总目录 C# 语法总目录 元组目录 元组1. 元组元素命名2. 元组的解构3. 元组的比较 元组 元组(tuple)是一组存储值的便捷方式。 元组的目的主要是&#xff0c;不使用out参数而从方法中返回多个值。(匿名类型无法做这个操作)元组能做匿名类型所有操作。 元组是值类型&#xff0…...

实用的Chrome 浏览器命令

Google Chrome 浏览器提供了许多快捷命令和实用功能&#xff0c;可以帮助用户提高效率和改善浏览体验。这里列举了一些非常实用的Chrome浏览器命令&#xff1a; 1. **CtrlT** / **CmdT** - 打开一个新的标签页。 2. **CtrlShiftT** / **CmdShiftT** - 重新打开最后关闭的标签页…...

IDEA远程连接docker服务,windows版docker desktop

1.windows上安装docker desktop docker desktop下载地址&#xff1a;Docker Desktop: The #1 Containerization Tool for Developers | Docker 有的windows系统不支持安装docker desktop 安装完之后我们可以直接打开&#xff0c;可以选择不登录使用 我们用IDEA连接到docker …...

Rust 和 Go 哪个更好?

在讨论 Rust 与 Go 两种编程语言哪种更优秀时&#xff0c;我们将探讨它们在性能、简易性、安全性、功能、规模和并发处理等方面的比较。同时&#xff0c;我们看看它们有什么共同点和根本的差异。现在就来看看这个友好而公平的对比。 Rust 和 Go 都是优秀的选择 首先&#xff…...

【免费Java系列】大家好 ,今天是学习面向对象高级的第八天点赞收藏关注,持续更新作品 !

这是java进阶课面向对象第一天的课程可以坐传送去学习http://t.csdnimg.cn/Lq3io day08-Map集合、Stream流、File类 一、Map集合 同学们&#xff0c;在前面几节课我们已经学习了Map集合的常用方法&#xff0c;以及遍历方式。 下面我们要学习的是Map接口下面的是三个实现类H…...

RPC 失败。curl 16 Error in the HTTP2 framing layer

报错&#xff1a; (base) hh-virtual-machine:~/work$ git clone https://github.com/yangzongzhuan/RuoYi-Vue3.git 正克隆到 RuoYi-Vue3... error: RPC 失败。curl 16 Error in the HTTP2 framing layer fatal: 在引用列表之后应该有一个 flush 包这个错误通常是由于 Git 在…...

(图论)最短路问题合集(包含C,C++,Java,Python,Go)

不存在负权边&#xff1a; 1.朴素dijkstra算法 原题&#xff1a; 思路&#xff1a;&#xff08;依然是贪心的思想&#xff09; 1.初始化距离&#xff1a;dis[1]0&#xff0c;dis[i]INF&#xff08;正无穷&#xff09; 2.循环n次&#xff1a; 找到当前不在s中的dis最小的点&…...

电脑文件批量重命名不求人:快速操作,高效技巧让你轻松搞定

在数字化时代&#xff0c;电脑文件的管理与整理显得尤为重要。当面对大量需要重命名的文件时&#xff0c;一个个手动修改不仅耗时&#xff0c;还容易出错。那么&#xff0c;有没有一种方法可以快速、高效地完成这一任务呢&#xff1f;答案是肯定的&#xff0c;下面就来介绍几种…...

基于springboot的网上点餐系统源码数据库

基于springboot的网上点餐系统源码数据库 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff1b;对于网上点餐系统当然也不能排除在外&#xff0c;随着网络技术的不断成熟&#xff0c;带动了网上点餐系统…...

mysql cluster数据库集群介绍、部署及配置

前言: MySQL集群是一个无共享的、分布式节点架构的存储方案,旨在提供容错性和高性能。它由三个主要节点组成:管理节点(MGM)、数据节点和SQL节点。 管理节点(MGM) 定义与用途:管理节点是MySQL Cluster的控制中心,负责管理集群内的其他节点。它提供配置数据,启动和停止…...

uniapp的app端软件更新弹框

1&#xff1a;使用html PLUS实现&#xff1a;地址HTML5 API Reference (html5plus.org)&#xff0c;效果图 2&#xff1a;在app.vue的onLaunch生命周期中&#xff0c;代码如下&#xff1a; onLaunch: function() {let a 0let view new plus.nativeObj.View(maskView, {backg…...

win11 Terminal 部分窗口美化

需求及分析&#xff1a;因为在 cmd、anaconda prompt 窗口中输入命令较多&#xff0c;而命令输入行和输出结果都是同一个颜色&#xff0c;不易阅读&#xff0c;故将需求定性为「美化窗口」。 美化结束后&#xff0c;我在想是否能不安装任何软件&#xff0c;简单地通过调整主题颜…...

开源go实现的iot物联网新基建平台

软件介绍 Magistrala IoT平台是由Abstract Machines公司开发的创新基础设施解决方案&#xff0c;旨在帮助组织和开发者构建安全、可扩展和创新的物联网应用程序。曾经被称为Mainflux的平台&#xff0c;现在已经开源&#xff0c;并在国际物联网领域受到广泛关注。 功能描述 多协…...

24深圳杯ABCD成品论文47页+各小问代码+图表

A题多个火箭残骸的准确定位&#xff1a; A题已经更新完22页完整版论文&#xff0b;高清无水印照片&#xff0b;Python&#xff08;MATLAB&#xff09;代码简单麦麦https://www.jdmm.cc/file/2710544/ 问题1&#xff1a;单个残骸的音爆位置确定 建模思路&#xff1a; 1. 声波传…...

doris经典bug

在部署完登录web页面查看的时候会发现只有一个节点可以读取信息剩余的节点什么也没读取到 在发现问题后&#xff0c;我们去对应的节点去看log日志&#xff0c;发现它自己绑定到前端的地址上了 现在我们已经发现问题了&#xff0c;以下就开始解决问题 重置doris 首先对be进行操…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

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

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

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...