LeetCode 15 —— 三数之和

阅读目录

    • 1. 题目
    • 2. 解题思路
    • 3. 代码实现

1. 题目

2. 解题思路

首先我们对数组进行从小到大排序,然后遍历数组 [ 0 , n u m s . s i z e ( ) − 3 ] [0,nums.size()-3] [0,nums.size()3] 作为三元组中的 a a a,由于三元组的索引互不相同,所以余下的 b b b c c c 我们则只能从 a a a 后面的元素中取,而且 b b b c c c 的索引也不能相同。

假设 a a a 取的是第 i i i 个元素,那么我们让 b b b 首先指向第 i + 1 i+1 i+1 个元素, c c c 首先指向第 n u m s . s i z e ( ) − 1 nums.size()-1 nums.size()1 个也即最后一个元素。这时候,我们检查 a + b + c a+b+c a+b+c 的和与零的关系。

  • 如果二者正好相等,我们保存这个三元组,同时让 b b b 向右移动一步,或者让 c c c 向左移动一步;
  • 如果和小于零,只能让 b b b 向右移动一步;
  • 如果和大于零,则只能让 c c c 向左移动一步。

同时,结果中不能包含重复的三元组,所以 a , b , c a, b,c abc 更新的时候我们都要确保它们不与上一次的值相同

排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn),求和时,最外层遍历 a a a 的时间复杂度为 O ( n ) O(n) O(n),内层遍历 b b b c c c 正好把数组访问一遍,时间复杂度也为 O ( n ) O(n) O(n),所以求和的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。所以,整体算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2),空间复杂度为 O ( 1 ) O(1) O(1)

3. 代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ret; 
        sort(nums.begin(), nums.end());
        int last = nums[0] - 1; // 上一个a,初始化为不和nums[0]相等即可
        for (int i = 0; i < nums.size()-2; ++i) {
            if (nums[i] == last) {
                continue;
            }
            int first = i + 1;
            int first_last_num = nums[first] - 1; // 上一个b,初始化为不和nums[first]相等即可
            int second = nums.size() - 1;
            int second_last_num = nums[second] + 1; // 上一个c,初始化为不和nums[second]相等即可
            while (first != second) {
                if (nums[first] == first_last_num) {
                    ++first;
                    continue;
                }
                if (nums[second] == second_last_num) {
                    --second;
                    continue;
                }
                int sum = nums[i] + nums[first] + nums[second];
                if (sum == 0) {
                    ret.push_back({nums[i], nums[first], nums[second]});
                    first_last_num = nums[first++]; // 更新上一次的b
                    second_last_num = nums[second]; // 更新上一次的c
                } else if (sum < 0) {
                    ++first;
                } else {
                    --second;
                }
            }
            last = nums[i]; // 更新上一次的a
        }
        return ret;
    }
};

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

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

相关文章

文件与IO基础常识知识

在这里&#xff0c;只介绍理论知识&#xff0c;不介绍代码。 目录 1.IO 1.1.字面概念 1.2.输入输出模型 2.文件 2.1.文件目录 2.2.文件路径 2.3.文件分类 1.IO 为了我们接下来学习的文件IO&#xff0c;所以我们先来认识什么是IO。 1.1.字面概念 &#xff08;1&#x…

【知识加油站】——机电产品数字孪生机理模型构建

明确一种多领域、多层次、参数化、一致性的机电一体化装备数字孪生机理模型构建准则&#xff01; 关键词英文简称&#xff1a; 数字孪生&#xff1a;DT物联网&#xff1a;IoT网络物理系统&#xff1a;CPS高级架构&#xff1a;HLA统一建模语言&#xff1a;UML数控机床&#xf…

Sarcasm detection论文解析 |A2Text-Net:一种用于讽刺检测的新型深度神经网络

论文地址 论文地址&#xff1a;A2Text-Net: A Novel Deep Neural Network for Sarcasm Detection | IEEE Conference Publication | IEEE Xplore github:lliyuan1117/A2Text-Net (github.com) 论文首页 A2Text-Net&#xff1a;一种用于讽刺检测的新型深度神经网络 &#x1f4c5…

Win11 怎么让软件运行后台全部显示在任务栏上 win11任务栏展开显示所有软件图标

Win11 怎么让软件运行后台全部显示在任务栏上 win11任务栏展开显示所有软件图标 方法二 搜索cmd 打开命令行面板 然后输入 explorer shell:::{05d7b0f4-2121-4eff-bf6b-ed3f69b894d9}就能显示出来了 ## 方法三 通知区域图标不存在 如图&#xff0c;显示为这样 这种时候桌面…

深入解析Java中的String对象及其性能优化

作者主页&#xff1a; &#x1f517;进朱者赤的博客 精选专栏&#xff1a;&#x1f517;经典算法 作者简介&#xff1a;阿里非典型程序员一枚 &#xff0c;记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法&#xff08;公众号同名&#xff09; ❤️觉得文章还…

uniapp乡村社区户籍问外来人员管理系统 微信小程序python+java+node.js+php

基于微信小程序的外来人员管理系统项目的概述设计分析&#xff0c;主要内容有的私教预约平台系统平台的具体分析&#xff0c;进行数据库的是设计&#xff0c;数据采用MySQL数据库&#xff0c;并且对于系统的设计采用比较人性化的操作设计&#xff0c;对于系统出现的错误信息可以…

用Jenkins Gerrit-Trigger插件实现提交gerrit后自动启动编译验证-解决编译依赖问题

用Jenkins Gerrit-Trigger插件实现提交gerrit后自动启动编译验证-CSDN博客讨论了如何利用插件在提交gerrit的时候自动出发一个jenkins job编译固件,但是没有解决编译依赖问题。本文提出一种解决方案 首先在git commit -m ""的时候在commit message中设置Depend-On:…

Typescript基础语法(四)

模块化 模块化是指将复杂的程序拆解为多个独⽴的⽂件单元&#xff0c;每个⽂件被称为⼀个模块。在 TypeScript 中&#xff0c;默认情况下&#xff0c;每个模块都拥有⾃⼰的作⽤域&#xff0c;这意味着在⼀个模块中声明的任何内容&#xff08;如变量、函数、类等&#xff09;在该…

我们的手机是如何连接上网的?骨干网又是什么?

什么是骨干网&#xff08;Backbone Network&#xff09; 几台计算机连接起来&#xff0c;互相可以看到其他人的文件&#xff0c;这叫局域网。整个城市的计算机都连接起来&#xff0c;就是城域网。把城市之间连接起来的网就叫骨干网。 这些骨干网是国家批准的可以直接和国外连…

CUDA CPP Unity Compute Shader

为学 开始一个新的学习计划&#xff0c;涵盖&#xff1a; 主题学习内容CUDAProfessional CUDA C Programming/NVIDIA CUDA初级教程视频(周斌)CCPrimer / The Cherno CPPUnity Compute ShaderUdemy Learn to Write Unity Compute ShadersLinear AlgebraMIT 18.06 Prof.Gilbert…

【Anaconda 3 】Jupyter Notebook 的安装配置及使用

Jupyter Notebook 的安装配置及使用 一、引言 Jupyter Notebook 是一种交互式笔记本&#xff0c;它允许用户将代码、注释、方程式、可视化内容等整合到一个文档中&#xff0c;并支持多种编程语言&#xff0c;如 Python、R、Julia 等。它在数据科学、机器学习和教育领域中得到…

Idea 自动生成测试

先添加测试依赖&#xff01;&#xff01; <!--Junit单元测试依赖--><dependency><groupId>org.junit.jupiter</groupId><artifactId>junit-jupiter</artifactId><version>5.9.1</version><scope>test</scope><…

MATLAB 集成

MATLAB 集成&#xff08;Integration&#xff09; 集成处理两种本质上不同的问题。 在第一种类型中&#xff0c;给出了函数的导数&#xff0c;我们想找到函数。因此&#xff0c;我们从根本上扭转了分化的过程。这种反向过程称为反微分&#xff0c;或者找到原始函数&#xff0…

基于SSM的宠物领养平台(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的宠物领养平台&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring Spri…

专项技能训练五《云计算网络技术与应用》实训7-1:安装mininet

文章目录 mininet安装1. 按6-1教程安装opendaylight控制器。2. 按6-2教程安装RYU控制器。3. 按5-1教程安装openvswitch虚拟交换机并开启服务。4. 将老师所给mininet安装包试用winSCP传送至电脑端。5. 安装net-tools。6. 安装mininet7. 安装完成后&#xff0c;使用命令建立拓扑&…

Stable Diffusion webUI 配置指南

Stable Diffusion webUI 配置指南 本博客主要介绍部署Stable Diffusion到本地&#xff0c;生成想要的风格图片。 文章目录 Stable Diffusion webUI 配置指南1、配置环境&#xff08;1&#xff09;pip环境[可选]&#xff08;2&#xff09;conda环境[可选] 2、配置Stable Diffu…

JavaScript 动态网页实例 —— 文字移动

前言 介绍文字使用的特殊效果。本章介绍文字的移动效果,主要包括:文字的垂直滚动、文字的渐隐渐显、文字的闪烁显示、文字的随意拖动、文字的坠落显示、页面内飘动的文字、漫天飞舞的文字、文字的下落效果。对于这些效果,读者只需稍加修改,就可以应用在自己的页面设计中。 …

农作物害虫检测数据集VOC+YOLO格式3575张10类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;3575 标注数量(xml文件个数)&#xff1a;3575 标注数量(txt文件个数)&#xff1a;3575 标注…

电话号码的字母组合 【C++】【力扣刷题】

解题思路&#xff1a; 以第一个为例,digits “23”&#xff0c;表明从电话号码的按键中选取2和3这两个字符&#xff0c;然后去寻找它们各自所对应的字母&#xff0c;这里每一个数字字符所对应的字母的不同&#xff0c;0对应的是空字符&#xff0c;而1的话题目中讲到是不对应任…

中药辨别二

声明&#xff1a;参考懒兔子公益课&#xff0c;参考网络资料和部分网络图片整理而成&#xff0c;仅供学习使用&#xff0c;不提供商业活动价值&#xff0c;文章描述的中药仅供学习&#xff0c;请在专业医师或专业医生指导下使用药材&#xff0c;擅自或其他情况下使用&#xff0…