双指针算法:三数之和

文章目录

    • 一、[题目链接:三数之和](https://leetcode.cn/problems/3sum/submissions/515727749/)
    • 二、思路讲解
    • 三、代码演示

在这里插入图片描述


先赞后看,养成习惯!!!^ _ ^<3 ❤️ ❤️ ❤️
码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了关注我哦!
所属专栏:双指针算法
在这里插入图片描述

一、题目链接:三数之和

在这里插入图片描述

二、思路讲解

方法一:暴力求解

我们只需要遍历所有情况即可得到所有结果,然后去重,由于时间复杂度比较高,过不了需要优化(O(3*n^3))

方法二:找规律
1.我们首先sort迭代器进行排序
2.排完序后我们开始遍历
3.如果从i=0开始遍历,left=i+1,right=n-1
4.优化:判断nums[i]是否大于0,大于0,后面的数都是单增的就直接break跳出
5.取nums[i]的相反数sum,判断sum和a[left]+a[right]的大小关系,如果sum大于a[left]+a[right],那么left++,小于的话就right–,同时要满足left<right
6.为了去重,判断下一个left和前一个left是否相同,下一个right和前一个right是否相同,相同就继续向前走,i也是
7.时间复杂度O(n^3+nlogn)

三、代码演示

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> arr;sort(nums.begin(),nums.end());int i = 0,n = nums.size();for(i=0;i<n;){if(nums[i]>0)break;int left = i+1,right = n-1,target = -nums[i];while(left<right){int sum = nums[left]+nums[right];if(sum>target) right--;else if(sum<target) left++;else{arr.push_back({nums[i],nums[left],nums[right]});left++,right--;while(left<right&&nums[left]==nums[left-1]) left++;while(left<right&&nums[right]==nums[right+1]) right--;}}i++;while(i<n&&nums[i]==nums[i-1]) i++;}return arr;}
};

在这里插入图片描述

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

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

相关文章

jmeter使用方法---自动化测试

HTTP信息头管理器 一个http请求会发送请求到服务器&#xff0c;请求里面包含&#xff1a;请求头、请求正文、请求体&#xff0c;请求头就是信息头Authorization头的主要用作http协议的认证。 Authorization的作用是当客户端访问受口令保护时&#xff0c;服务器端会发送401状态…

【RPG Maker MV 仿新仙剑 战斗场景UI (八)】

RPG Maker MV 仿新仙剑 战斗场景UI 八 状态及装备场景代码效果 状态及装备场景 本计划在战斗场景中直接制作的&#xff0c;但考虑到在战斗场景中加入太多的窗口这不太合适&#xff0c;操作也繁琐&#xff0c;因此直接使用其他场景。 代码 Pal_Window_EquipStatus.prototype.…

TXT文件内容轻松整理,一键删除文本里的多个内容,轻松整理文档!

在数字化时代&#xff0c;TXT文件已成为我们日常工作和学习的常见文档格式。然而&#xff0c;随着时间的推移&#xff0c;这些文档中可能会积累大量的冗余内容&#xff0c;如重复的文字、无用的注释或不必要的空格。手动删除这些内容不仅费时费力&#xff0c;还可能遗漏或误删重…

【高并发服务器 01】—— 基础知识回顾

接下来四周时间&#xff0c;我将会做一个高并发服务器相关的项目。 前置知识&#xff1a;操作系统系统编程、网络编程、基础的数据结构、C语言。 开发环境&#xff1a;VMware虚拟机&#xff1a;Ubuntu 20.04.6 LTS、vscode 今天先回顾一些基础知识。 1.文件与IO 标准IO&#…

uni-app从零开始快速入门

教程介绍 跨端框架uni-app作为新起之秀&#xff0c;在不到两年的时间内&#xff0c;迅速被广大开发者青睐和推崇&#xff0c;得益于它颠覆性的优势“快”&#xff0c;快到可以节省7套代码。本课程由uni-app开发者团队成员亲授&#xff0c;带领大家无障碍快速掌握完整的uni-app…

pandas的综合练习

事先说明&#xff1a; 由于每次都要导入库和处理中文乱码问题&#xff0c;我都是在最前面先写好&#xff0c;后面的代码就不在写了。要是copy到自己本地的话&#xff0c;就要把下面的代码也copy下。 # 准备工作import pandas as pd import numpy as np from matplotlib impor…

linux源配置:ubuntu、centos;lspci与lsmod命令区别

1、ubuntu源配置 1&#xff09;先查电脑版本型号: lsb_release -c2&#xff09;再编辑源更新&#xff0c;源要与上面型号对应 参考&#xff1a;https://midoq.github.io/2022/05/30/Ubuntu20-04%E6%9B%B4%E6%8D%A2%E5%9B%BD%E5%86%85%E9%95%9C%E5%83%8F%E6%BA%90/ /etc/apt/…

【Docker】golang操作容器使用rename动态更新容器的名字

【Docker】golang操作容器使用rename动态更新容器的名字 大家好 我是寸铁&#x1f44a; 总结了一篇golang操作容器使用rename动态更新容器的名字✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 前言 今天遇到一个新的需求&#xff0c;要动态改变运行中的容器名字。 可以考虑先把…

数据结构/C++:哈希表

数据结构/C&#xff1a;哈希表 哈希表概念哈希函数直接定址法除留余数法 哈希冲突闭散列 - 开放定址法基本结构查找插入删除总代码展示 开散列 - 哈希桶基本结构查找插入删除代码展示 哈希表概念 在顺序表中&#xff0c;查找一个数据的时间复杂度为O(N)&#xff1b;在平衡树这…

数据仓库相关概述

数据仓库概述 数据仓库概念 数据仓库是一个为数据分析而设计的企业级数据管理系统。数据仓库可集中、整合多个信息源的大量数据&#xff0c;借助数据仓库的分析能力&#xff0c;企业可从数据中获得宝贵的信息进而改进决策。同时&#xff0c;随着时间的推移&#xff0c;数据仓…

3个Tips,用“AI”开启新生活

相信最近&#xff0c;很多朋友们都回归到了忙碌的生活节奏中。生活模式的切换&#xff0c;或多或少会带来身体或情绪状况的起伏。新技术正在为人们生活的方方面面带来便利。3个小Tips或许能让你也从新技术中获益&#xff0c;从身到心&#xff0c;用“AI”开启新生活。 关”A…

【Linux杂货铺】进程控制

目录 &#x1f308;前言&#x1f308; &#x1f4c1; 进程创建 &#x1f4c2; fork函数 &#x1f4c2; 写实拷贝 &#x1f4c2; 创建进程的目的 &#x1f4c2; 创建失败原因 &#x1f4c1; 进程终止 &#x1f4c2; 概念 &#x1f4c2; 场景 &#x1f4c2; 退出方法 …

使用React搭建single-spa

自己搭建的Demo GitHub - ftao123/single-spa-react-demo: single-spa-react-demo 修改子应用的webpack配置 library: "app2"和libraryTarget: "umd"配置必须添加。 可以看到filename在开发环境下的地址是static/js/bundle.js&#xff0c;所以我们主应用…

【Delphi JCL库文件解剖 1】库文件的大体脉络

JCL库是一个开源的Delphi库文件,下载到它很容易,可是想能灵活运用它却并不容易。下面是这个库文件的大体文件脉络,咱们要分析的核心还是在 source 源代码文件。 bin - 示例应用程序可执行文件的常见位置 docs - 读…

JavaEE-文件操作和IO

我们先来认识狭义上的⽂件(file)。针对硬盘这种持久化存储的I/O设备&#xff0c;当我们想要进⾏数据保存时&#xff0c;往往不是保存成⼀个整体&#xff0c;⽽是独⽴成⼀个个的单位进⾏保存&#xff0c;这个独⽴的单位就被抽象成⽂件的概念&#xff0c;就类似办公桌上的⼀份份真…

Java程序设计 4、5章 练习题

一、填空题 1.假设有 String s1 "Welcome to Java"; String s2 s1; String s3 new String("Welcome to Java"); 那么下面表达式的结果是什么&#xff1f; (1) s1 s2 ___________true_______________ (2) s1 s3 ______…

C++ Thread 源码 观后 自我感悟 整理

Thread的主要数据成员为_Thr 里面存储的是线程句柄和线程ID 先看看赋值运算符的移动构造 最开始判断线程的ID是否不为0 _STD就是使用std的域 如果线程ID不为0&#xff0c;那么就抛出异常 这里_New_val使用了完美转发&#xff0c;交换_Val和_New_val的值 _Thr _STD exchange(_…

【动手学深度学习】深入浅出深度学习之PyTorch基础

目录 一、实验目的 二、实验准备 三、实验内容 1. 数据操作 2. 数据预处理 3. 线性代数 4. 微积分 5. 自动微分 四、实验心得 一、实验目的 &#xff08;1&#xff09;正确理解深度学习所需的数学知识&#xff1b; &#xff08;2&#xff09;学习一些关于数据的实用…

如何设置Word文档的高级属性?这里有详细步骤

我们最近向你展示了如何在Word中设置用户信息。Word还存储与文档相关的几个其他高级属性。其中一些显示在“信息”屏幕上&#xff0c;你可以更改这些属性。 注意&#xff1a;我们使用Word 2013来说明此功能。 要访问允许你更改当前打开文档的属性的对话框&#xff0c;请单击“…

使用 Amazon SageMaker 微调 Llama 2 模型

本篇文章主要介绍如何使用 Amazon SageMaker 进行 Llama 2 模型微调的示例。 这个示例主要包括: Llama 2 总体介绍Llama 2 微调介绍Llama 2 环境设置Llama 2 微调训练 前言 随着生成式 AI 的热度逐渐升高&#xff0c;国内外各种基座大语言竞相出炉&#xff0c;在其基础上衍生出…