面试经典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 题目来源我的题解方法一 暴力解法 超时方法二 扩展两数之和(双指针)方法三 扩展为通用的n数之和 题目来源 力扣每日一题;题序:15 我的题解 方法一 暴力解法 超时 进行三重循环遍历,判断和是否为…...
go动态创建/增加channel并处理数据
背景描述 有一个需求,大概可以描述为:有多个websocket连接,因此消息会并发地发送过来,这些消息中有一个标志可以表明是哪个连接发来的消息,但只有收到消息后才能建立channel或写入已有channel,在收消息前无…...
asp.net成绩查询系统
说明文档 运行前附加数据库.mdf(或sql生成数据库) 主要技术: 基于asp.net架构和sql server数据库 功能模块: asp.net成绩查询系统 学生功能有查看成绩和修改账号密码等 后台管理员可以进行用户管理 管理员添加管理员查询注…...
Express路由
什么是路由 官方定义:路由确定了应用程序如何响应客户端对特定端点的请求。 路由的使用 一个路由的组成有 请求方法、路径 和 回调函数 组成。 Express中提供了一些列方法,可以很方便的使用路由,使用格式如下: app.<metho…...
在做题中学习(53): 寻找旋转数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode) 解法:O(logn)->很可能就是二分查找 思路:再看看题目要求,可以画出旋转之后数组中元素的大小关系: 首先,数组是具有二段性的(适配二分查…...
C#语言进阶(三) 元组
总目录 C# 语法总目录 元组目录 元组1. 元组元素命名2. 元组的解构3. 元组的比较 元组 元组(tuple)是一组存储值的便捷方式。 元组的目的主要是,不使用out参数而从方法中返回多个值。(匿名类型无法做这个操作)元组能做匿名类型所有操作。 元组是值类型࿰…...
实用的Chrome 浏览器命令
Google Chrome 浏览器提供了许多快捷命令和实用功能,可以帮助用户提高效率和改善浏览体验。这里列举了一些非常实用的Chrome浏览器命令: 1. **CtrlT** / **CmdT** - 打开一个新的标签页。 2. **CtrlShiftT** / **CmdShiftT** - 重新打开最后关闭的标签页…...
IDEA远程连接docker服务,windows版docker desktop
1.windows上安装docker desktop docker desktop下载地址:Docker Desktop: The #1 Containerization Tool for Developers | Docker 有的windows系统不支持安装docker desktop 安装完之后我们可以直接打开,可以选择不登录使用 我们用IDEA连接到docker …...
Rust 和 Go 哪个更好?
在讨论 Rust 与 Go 两种编程语言哪种更优秀时,我们将探讨它们在性能、简易性、安全性、功能、规模和并发处理等方面的比较。同时,我们看看它们有什么共同点和根本的差异。现在就来看看这个友好而公平的对比。 Rust 和 Go 都是优秀的选择 首先ÿ…...
【免费Java系列】大家好 ,今天是学习面向对象高级的第八天点赞收藏关注,持续更新作品 !
这是java进阶课面向对象第一天的课程可以坐传送去学习http://t.csdnimg.cn/Lq3io day08-Map集合、Stream流、File类 一、Map集合 同学们,在前面几节课我们已经学习了Map集合的常用方法,以及遍历方式。 下面我们要学习的是Map接口下面的是三个实现类H…...
RPC 失败。curl 16 Error in the HTTP2 framing layer
报错: (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)
不存在负权边: 1.朴素dijkstra算法 原题: 思路:(依然是贪心的思想) 1.初始化距离:dis[1]0,dis[i]INF(正无穷) 2.循环n次: 找到当前不在s中的dis最小的点&…...
电脑文件批量重命名不求人:快速操作,高效技巧让你轻松搞定
在数字化时代,电脑文件的管理与整理显得尤为重要。当面对大量需要重命名的文件时,一个个手动修改不仅耗时,还容易出错。那么,有没有一种方法可以快速、高效地完成这一任务呢?答案是肯定的,下面就来介绍几种…...
基于springboot的网上点餐系统源码数据库
基于springboot的网上点餐系统源码数据库 随着科学技术的飞速发展,各行各业都在努力与现代先进技术接轨,通过科技手段提高自身的优势;对于网上点餐系统当然也不能排除在外,随着网络技术的不断成熟,带动了网上点餐系统…...
mysql cluster数据库集群介绍、部署及配置
前言: MySQL集群是一个无共享的、分布式节点架构的存储方案,旨在提供容错性和高性能。它由三个主要节点组成:管理节点(MGM)、数据节点和SQL节点。 管理节点(MGM) 定义与用途:管理节点是MySQL Cluster的控制中心,负责管理集群内的其他节点。它提供配置数据,启动和停止…...
uniapp的app端软件更新弹框
1:使用html PLUS实现:地址HTML5 API Reference (html5plus.org),效果图 2:在app.vue的onLaunch生命周期中,代码如下: onLaunch: function() {let a 0let view new plus.nativeObj.View(maskView, {backg…...
win11 Terminal 部分窗口美化
需求及分析:因为在 cmd、anaconda prompt 窗口中输入命令较多,而命令输入行和输出结果都是同一个颜色,不易阅读,故将需求定性为「美化窗口」。 美化结束后,我在想是否能不安装任何软件,简单地通过调整主题颜…...
开源go实现的iot物联网新基建平台
软件介绍 Magistrala IoT平台是由Abstract Machines公司开发的创新基础设施解决方案,旨在帮助组织和开发者构建安全、可扩展和创新的物联网应用程序。曾经被称为Mainflux的平台,现在已经开源,并在国际物联网领域受到广泛关注。 功能描述 多协…...
24深圳杯ABCD成品论文47页+各小问代码+图表
A题多个火箭残骸的准确定位: A题已经更新完22页完整版论文+高清无水印照片+Python(MATLAB)代码简单麦麦https://www.jdmm.cc/file/2710544/ 问题1:单个残骸的音爆位置确定 建模思路: 1. 声波传…...
doris经典bug
在部署完登录web页面查看的时候会发现只有一个节点可以读取信息剩余的节点什么也没读取到 在发现问题后,我们去对应的节点去看log日志,发现它自己绑定到前端的地址上了 现在我们已经发现问题了,以下就开始解决问题 重置doris 首先对be进行操…...
贪心算法应用例题
最优装载问题 #include <stdio.h> #include <algorithm>//排序int main() {int data[] { 8,20,5,80,3,420,14,330,70 };//物体重量int max 500;//船容最大总重量int count sizeof(data) / sizeof(data[0]);//物体数量std::sort(data, data count);//排序,排完数…...
亚信科技精彩亮相2024中国移动算力网络大会,数智创新共筑“新质生产力”
4月28至29日,江苏省人民政府指导、中国移动通信集团有限公司主办的2024中国移动算力网络大会在苏州举办。大会以“算力网络点亮AI时代”为主题,旨在凝聚生态伙伴合力,共同探索算力网络、云计算等数智能力空间,共促我国算网产业和数…...
图像处理中的颜色空间转换
在图像处理中,颜色空间转换是指将图像从一种颜色表示方式转换为另一种颜色表示方式。常见的颜色空间转换包括RGB到HSV、RGB到灰度、RGB到CMYK等。 RGB到HSV转换: RGB颜色空间由红色(R)、绿色(G)和蓝色&…...
网络安全之静态路由
以下是一个静态路由的拓扑图 Aping通B,C可以ping通D。 路由器转发数据需要路由表,但仍可以Aping通B,C可以ping通D,是因为产生了直连路由:产生的条件有两个,接口有IP,接口双up(物理upÿ…...
Golang | Leetcode Golang题解之第74题搜索二维矩阵
题目: 题解: func searchMatrix(matrix [][]int, target int) bool {m, n : len(matrix), len(matrix[0])i : sort.Search(m*n, func(i int) bool { return matrix[i/n][i%n] > target })return i < m*n && matrix[i/n][i%n] target }...
2023黑马头条.微服务项目.跟学笔记(五)
2023黑马头条.微服务项目.跟学笔记 五 延迟任务精准发布文章 1.文章定时发布2.延迟任务概述 2.1 什么是延迟任务2.2 技术对比 2.2.1 DelayQueue2.2.2 RabbitMQ实现延迟任务2.2.3 redis实现3.redis实现延迟任务4.延迟任务服务实现 4.1 搭建heima-leadnews-schedule模块4.2 数据库…...
C语言 | Leetcode C语言题解之第75题颜色分类
题目: 题解: void swap(int *a, int *b) {int t *a;*a *b, *b t; }void sortColors(int *nums, int numsSize) {int p0 0, p2 numsSize - 1;for (int i 0; i < p2; i) {while (i < p2 && nums[i] 2) {swap(&nums[i], &num…...
淘宝扭蛋机小程序开发:掌上惊喜,转出你的幸运宝藏
一、全新玩法,尽在掌中 淘宝扭蛋机小程序,将传统的扭蛋乐趣与数字时代完美结合,为您带来全新的购物体验。在这个小小的平台上,您可以用手指轻松操控,探索无尽的宝藏世界,转出专属于您的幸运好物。 二、海…...
Oracle索引组织表与大对象平滑迁移至OceanBase的实施方案
作者简介:严军(花名吉远),十年以上专注于数据库存储领域,精通Oracle、Mysql、OceanBase,对大数据、分布式、高并发、高性能、高可用有丰富的经验。主导过蚂蚁集团核心系统数据库升级,数据库LDC单元化多活项目ÿ…...
【服务治理中间件】consul介绍和基本原理
目录 一、CAP定理 二、服务注册中心产品比较 三、Consul概述 3.1 什么是Consul 3.2 Consul架构 3.3 Consul的使用场景 3.4 Consul健康检查 四、部署consul集群 4.1 服务器部署规划 4.2 下载解压 4.3 启动consul 五、服务注册到consul 一、CAP定理 CAP定理ÿ…...
无人机运营合格证:民用无人机驾驶航空器运营合格证书
无人机运营合格证是指经国家相关部门审核通过并颁发给相应无人驾驶航空器运营机构的一种资质证明。获得该证书的机构具备相关的技术和管理能力,能够安全、合规地运营无人驾驶航空器。 无人机运营合格证的申请流程一般包括报名、培训学习、考试准备、考试报名、考试…...
【编码利器 —— BaiduComate】
目录 1. 智能编码助手介绍 2. 场景需求 3. 功能体验 3.1指令功能 3.2插件用法 3.3知识用法 3.4自定义配置 4. 试用感受 5. AI编程应用 6.总结 智能编码助手是当下人工智能技术在编程领域的一项重要应用。Baidu Comate智能编码助手作为一款具有强大功能和智能特性的工…...
python 关键字(in)
9、in 在Python中,in关键字是一个强大的工具,用于检查一个元素是否存在于某个序列(如列表、元组、字符串等)或集合(如集合、字典的键)中。 基础小白知识:in的基本用法 1.1 在序列中检查元素 …...
【Node.js从基础到高级运用】二十八、Node.js 内存管理浅析
Node.js 作为一个基于 Chrome V8 引擎的 JavaScript 运行环境,其性能和效率在很大程度上取决于内存管理的优劣。 1. Node.js 内存结构 在深入了解内存管理之前,我们需要先了解 Node.js 的内存结构。Node.js 的内存可以大致分为以下几个部分:…...
AES加密解密
加密 java.util.Base64; javax.crypto.Cipher; javax.crypto.spec.SecretKeySpec; // 入参:data(String)、seed(String) Cipher cipher Cipher.getInstance("AES/ECB/PKCS5Padding"); SecretKeySpec secre…...
通过红黑树封装 map 和 set 容器(1):红黑树的迭代器
一、红黑树的迭代器 红黑树的遍历默认为中序遍历 —— key 从小到大,因此 begin() 应该获取到红黑树的最左节点 —— 最小,end() 获取到红黑树最右节点的下一个位置, operator() 也应保证红黑树的遍历为中序的状态。 首先对红黑树节点进行改造…...
mysqlbinlog恢复delete的数据
实验目的 delete数据后,用mysqlbinlog进行数据恢复 实验过程 原表 mysql> select * from mytest; ----------------- | id | name | score | ----------------- | 1 | xw01 | 90 | | 2 | xw02 | 92 | | 3 | xw03 | 93 | | 4 | xw04 | 94 | |…...
传递给组件
React 组件使用 props 相互通信。每个父组件都可以通过为其子组件提供道具来将一些信息传递给子组件。Props 可能会让您想起 HTML 属性,但您可以通过它们传递任何 JavaScript 值,包括对象、数组和函数。 Props 是传递给 JSX 标签的信息。例如࿰…...
鸿蒙通用组件弹窗简介
鸿蒙通用组件弹窗简介 弹窗----Toast引入ohos.promptAction模块通过点击按钮,模拟弹窗 警告对话框----AlertDialog列表弹窗----ActionSheet选择器弹窗自定义弹窗使用CustomDialog声明一个自定义弹窗在需要使用的地方声明自定义弹窗,完整代码 弹窗----Toa…...
[译文] 恶意代码分析:1.您记事本中的内容是什么?受感染的文本编辑器notepad++
这是作者新开的一个专栏,主要翻译国外知名安全厂商的技术报告和安全技术,了解它们的前沿技术,学习它们威胁溯源和恶意代码分析的方法,希望对您有所帮助。当然,由于作者英语有限,会借助LLM进行校验和润色&am…...
Spring Boot3.x集成Disruptor4.0
Disruptor介绍 Disruptor是一个高性能内存队列,研发的初衷是解决内存队列的延迟问题(在性能测试中发现竟然与I/O操作处于同样的数量级)。基于Disruptor开发的系统单线程能支撑每秒600万订单,2010年在QCon演讲后,获得了业界关注。2011年&…...
GoEdge自建CDN工具
GoEdge是一款管理分布式CDN边缘节点的开源工具软件,可以让用户轻松地、低成本地创建CDN/WAF等应用。同时提供免费版本和商业版本,本文基本免费版本安装测试。 GoEdgep安装涉及三部分: 边缘节点 - 接收和响应用户请求的终端节点 管理员系统 - …...
牛客储物点的距离
链接:登录—专业IT笔试面试备考平台_牛客网 来源:牛客网 题目描述 一个数轴,每一个储物点会有一些东西,同时它们之间存在距离。 每次给个区间[l,r],查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少࿱…...
【C++历练之路】红黑树——map与set的封装实现
W...Y的个人主页💕 gitee代码仓库分享😊 前言:上篇博客中,我们为了使二叉搜索树不会出现”一边倒“的情况,使用了AVL树对搜索树进行了处理,从而解决了数据在有序或者接近有序时出现的情况。但是AVL树还会…...
RDB快照是怎么实现的?
RDB快照是怎么实现的? 前言快照怎么用?执行快照时,数据能被修改吗?RDB 和 AOF 合体 前言 虽说 Redis 是内存数据库,但是它为数据的持久化提供了两个技术。 分别是「 AOF 日志和 RDB 快照」。 这两种技术都会用各用一…...
智能体可靠性的革命性提升,揭秘知识工程领域的参考架构新篇章
引言:知识工程的演变与重要性 知识工程(Knowledge Engineering,KE)是一个涉及激发、捕获、概念化和形式化知识以用于信息系统的过程。自计算机科学和人工智能(AI)历史以来,知识工程的工作流程因…...
Shell 初始化配置指北 | Ubuntu
唠唠闲话 概要:在不同的Shell环境(如Bash和Zsh)中设置环境变量、设置初始脚本,以及如何根据不同的使用场景(用户级或系统级)管理和设置初始运行命令。 p.s. 如果你很熟悉 Linux,推荐跳到最后一…...
[嵌入式系统-69]:RT-Thread-组件:网络组件“组”,RT-Thread系统通向外部网络世界的入口
目录 RT-Thread 提供的网络世界入口 - 网络组件 1. 总概 2. AT 3. Lwip: 轻量级IP协议栈 4. W5500 5. Netdev 6. RT-Thread SAL(Socket Abstraction Layer)套接字和BSD套接字区别 RT-Thread SAL 套接字接口示例 BSD 套接字接口示例 …...
Linux学习笔记1---Windows上运行Linux
在正点原子的教程中学习linux需要安装虚拟机或者在电脑上安装一个Ubuntu系统,但个人觉得太麻烦了,现在linux之父加入了微软,因此在Windows上也可以运行linux 了。具体方法如下: 一、 在Windows上的设置 在window的搜索框内&#…...
Java算法-力扣leetcode-135. 分发糖果
135. 分发糖果 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求,给这些孩子分发糖果: 每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果,计算并…...
通过http协议上传或下载文件,客户端和服务端是如何协商保持长时间的http链接的
在通过HTTP协议上传或下载大文件时,客户端和服务端需要确保连接在整个传输过程中保持活跃。为了实现这一点,HTTP协议以及客户端和服务端软件(如浏览器和服务器)提供了一些机制来协商和维持长时间的HTTP连接。以下是主要的机制和方…...
前端启若依项目 后端配置 若依
...
ue引擎游戏开发笔记(41)——行为树的建立(2)--丰富ai行为:巡逻后返回原处
1.需求分析: 就敌人ai而言,追踪到敌人有可能丢失目标,丢失目标后应该能返回原来位置,实现这一功能。 2.操作实现: 1.思路:利用clear value函数,禁用掉当前的追踪功能,执行之后的返…...
程序员的实用神器之——通义灵码
通义灵码介绍 “通义灵码”是一款基于阿里云通义代码大模型打造的智能编码助手,产品于2023年10月31日云栖大会上,正式对外发布。新手亦能驾轻,老手恒常运,唯手熟尔。 通义灵码产品介绍_智能编码助手_AI编程_云效(Apsara Devops)…...
Windows 10无法远程桌面连接:原因及解决方案
在信息技术日益发展的今天,远程桌面连接已成为企业日常运维、技术支持乃至个人用户远程办公的必备工具。然而,有时我们可能会遇到Windows 10无法远程桌面连接的问题,这无疑会给我们的工作和生活带来诸多不便。 原因分析 1、远程访问未启用&a…...
算法学习笔记(5.0)-基于比较的高效排序算法-归并排序
##时间复杂度O(nlogn) 目录 ##时间复杂度O(nlogn) ##递归实现归并排序 ##原理 ##图例 ##代码实现 ##非递归实现归并排序 ##释 #代码实现 ##递归实现归并排序 ##原理 是一种基于分治策略的基础排序算法。 1.划分阶段:通过不断递归地将数组从中点处分开&…...