【三数之和】python,排序+双指针

news/2024/7/25 20:19:35/文章来源:https://blog.csdn.net/m0_73629042/article/details/139161003

暴力搜索3次方的时间复杂度,大抵超时

遇到不会先排序

排序+双指针

上题解

照做

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:res=[]n=len(nums)#排序降低复杂度nums.sort()k=0#留两个位置给双指针i,jfor k in range(n-2):if nums[k]>0:break#比较其和前一个元素是否相等,相等则跳过(防止重复)if k>0 and nums[k]==nums[k-1]:continuei=k+1j=n-1while i<j:sum=nums[k]+nums[i]+nums[j]if sum<0:i+=1#同样的结果了while i<j and nums[i]==nums[i-1]:i+=1elif sum>0:j-=1#一样while i<j and nums[j]==nums[j+1]:j-=1else:res.append([nums[k],nums[i],nums[j]])i+=1j-=1#samewhile i<j and nums[i]==nums[i-1]:i+=1while i<j and nums[j]==nums[j+1]:j-=1return res

过 

 

总结:

  1. 数组排序
  2. 固定一个数,开始双指针,第一个指针紧随其后,第二个指针逆序
  3. 剪枝包括与前面的元素相比有没有相同,相同则跳过
  4. 每次移动i/j都可以考虑刚刚那步的剪枝 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1052178.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【上】王树森《小红书推荐系统公开课》- 课程笔记(推荐系统基础、召回、排序)

写在前面 本文为王树森老师《小红书推荐系统公开课》的课程笔记 课程来源&#xff1a;ShusenWang的个人空间-ShusenWang个人主页-哔哩哔哩视频 (bilibili.com)课程资料&#xff1a;GitHub - wangshusen/RecommenderSystem 由于篇幅较长&#xff0c;分为【上】【下】两篇文章…

Autodesk Flame 2025 for Mac:视觉特效制作的终极利器

在数字时代&#xff0c;视觉特效已经成为电影、电视制作中不可或缺的一部分。Autodesk Flame 2025 for Mac&#xff0c;这款专为视觉特效师打造的终极工具&#xff0c;将为您的创作提供无尽的可能。 Autodesk Flame 2025 for Mac拥有强大的三维合成环境&#xff0c;能够支持您…

ROS for LabVIEW:实现LabVIEW与ROS的无缝集成

ROS for LabVIEW是由Tufts大学开发的一套VI集合&#xff0c;旨在实现LabVIEW与ROS&#xff08;Robot Operating System&#xff09;的无缝集成。ROS是一个灵活的机器人软件框架&#xff0c;而LabVIEW则是一种强大的图形化编程工具。这个工具包的推出使得LabVIEW用户能够直接与R…

【吊打面试官系列】Java高并发篇 - 线程的调度策略?

大家好&#xff0c;我是锋哥。今天分享关于 【线程的调度策略?】面试题&#xff0c;希望对大家有帮助&#xff1b; 线程的调度策略? 线程调度器选择优先级最高的线程运行&#xff0c;但是&#xff0c;如果发生以下情况&#xff0c;就会终止线程的运行&#xff1a; 1、线程体…

基于jeecgboot-vue3的Flowable增加流程支持组件与element-plus组件导入支持

因为这个项目license问题无法开源&#xff0c;更多技术支持与服务请加入我的知识星球。 1、package.json文件需要增加相关流程组件&#xff0c;如下 "dependencies": {"element-plus/icons-vue": "^2.3.1","highlightjs/vue-plugin":…

BEVFormer论文详细解读

文章目录 1. 前言1.1 3D VS 4D1.2 .特征融合过程中可能遇到的问题1.3 .BEV提出背景1.4 .BEV最终得到了什么1.5 .输入数据格式 2. 背景/Motivation2.1 为什么视觉感知要用BEV&#xff1f;2.2 生成BEV视角的方法有哪些&#xff1f;为何选用Transformer呢&#xff1f; 3. Method/S…

【Typescript】通过变量的值即可获取变量的类型【typeof 变量】

注意&#xff1a;只要变量的类型准确,则typeof获取变量的类型就不会错 enum Test {a "a0",b "b0" }// 这里的a是一个变量的值 let a: Test.a "a0" as Test.a// 这里的typeof a是一个类型【Test.a】 let x: typeof a Test.a

基于Cortex的MCU设计

基于Cortex的MCU设计 今日更新的存货文档&#xff0c;发现日更文章还是很花时间的。保证一周更新三篇文章就行啦&#xff0c;本篇文章的内容起始主要取自于《Cortex-M3 权威指南》和知网下载的论文。写的不详细&#xff0c;想进一步了解的就去看这篇文档或网上找别的资料&#…

3.5 四个子空间的维度

一、概述 这一节的主要定理是将秩与维度联系在一起。矩阵的秩就是主元的个数&#xff0c;子空间的维度是基向量的个数&#xff0c;我们计算出这两个数就可以得到秩与维度。 A A A 的秩揭露了四个基本子空间的维度。 四个子空间中&#xff0c;两个子空间来自 A A A&#xff0c…

C++ 函数模板与模板函数

一 代码重用技术 函数 类与对象 继承与派生 多态&#xff08;函数重载、运算符重载、虚函数、纯虚函数与抽象类&#xff09; 泛型程序设计 通用的代码需要补受数据类型的影响&#xff0c;并且可以自动适应数据类型的变化&#xff0c;这种程序设计类型称为泛型程序设计。 二 模…

雷军-2022.8小米创业思考-9-爆品模式:产品力超群,具有一流口碑,最终实现海量长销的产品。人人都向往;做减法;重组创新;小白模式

第九章 爆品模式 小米方法论的第三个关键词&#xff0c;就是一切以产品为出发点&#xff0c;打造爆品模式。 大多数人对“爆品”的着眼点仅在于“爆”&#xff0c;也就是产品卖得好。希望产品大卖这没有错&#xff0c;但是“爆”是“品”的结果&#xff0c;爆品是打造出来的&…

服务器软件架构演进

服务器软件架构演进 背景介绍阶段一&#xff1a;单机部署阶段二&#xff1a;应用与数据分离部署阶段三&#xff1a;启用缓存优化阶段四&#xff1a;启用应用服务器集群阶段五&#xff1a;数据库读写分离阶段六&#xff1a;启用反向代理及CDN加速阶段七&#xff1a;启用分布式文…

探索亚马逊云科技技术课程:大模型平台与提示工程的应用与优化

上方图片源自亚马逊云科技【生成式 AI 精英速成计划】技术开发技能课程 前言 学习了亚马逊云科技–技术开发技能课程 本课程分为三个部分&#xff0c;了解如何使用大模型平台、如何训练与部署大模型及生成式AI产品应用与开发&#xff0c;了解各类服务的优势、功能、典型使用案…

【简单介绍下容器是什么?】

&#x1f3a5;博主&#xff1a;程序员不想YY啊 &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 ✨希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出…

专为汽车内容打造的智能剪辑解决方案

汽车内容创作已成为越来越多车主和汽车爱好者热衷的活动。然而&#xff0c;如何高效、便捷地将行车途中的精彩瞬间转化为高质量的视频作品&#xff0c;一直是困扰着广大用户的一大难题。美摄科技凭借其深厚的视频处理技术和智能分析能力&#xff0c;推出了专为汽车内容记录而生…

斯洛文尼亚普利雅玛城堡:吉尼斯世界纪录认证的世界最大溶洞城堡

除了著名的波斯托伊纳溶洞&#xff08;Postojna Cave&#xff09;&#xff0c;普利雅玛城堡&#xff08;Predjama Castle&#xff09;也是波斯托伊纳洞穴公园&#xff08;Postojna Cave Park&#xff09;不容错过的景点之一。这座城堡坐落在斯洛文尼亚&#xff08;Slovenia&…

Java入门基础学习笔记47——ArrayList

什么是集合呢&#xff1f; 集合是一种容器&#xff0c;用来装数据的&#xff0c;类似数组。 有数组&#xff0c;为什么还要学习集合呢&#xff1f; 数组定义完成并启动后&#xff0c;长度就固定了。 而集合是大小可变&#xff0c;开发中用的最多的。 集合的特点&#xff1a;大…

基于docxtpl的模板生成Word

docxtpl是一个用于生成Microsoft Word文档的模板引擎库。它结合了docx模块和Jinja2模板引擎&#xff0c;使用户能够使用Microsoft Word模板文件并在其中填充动态数据。这个库提供了一种方便的方式来生成个性化的Word文档&#xff0c;并支持条件语句、循环语句和变量等控制结构&…

从零开始构建 Vision Transformer(ViT) 模型

Transformer 模型最早由 Vaswani 等人在 2017 年论文 Attention Is All You Need 中提出&#xff0c;并已广泛应用于自然语言处理。 2021年&#xff0c;Dosovitsky 等人在论文An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale中提出将 Transforme…

PyQt5-新手避坑指南(持续更新)

文章目录 一&#xff0e;前言二&#xff0e;开发环境三&#xff0e;坑1.程序没有详细报错就退出了2.qrc资源文件的使用3.QLabel文字自动换行4.图片自适应大小5.checkbox自定义样式后✓不见了6.多线程 四&#xff0e;记录 一&#xff0e;前言 本篇博客整理了一些初学者容易犯的…