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

对撞双指针(七)三数之和

15. 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

首先利用双指针思想进行寻找合适的三个数,再利用set进行去重。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();set<vector<int>> res;sort(nums.begin(), nums.end());for(int i = n-1; i > 1; i--){int c = nums[i];int temp = 0-c;int left = 0, right = i-1;while(left < right){if(nums[left] + nums[right] < temp)left++;else if(nums[left] + nums[right] > temp)right--;else{res.insert({nums[left], nums[right], c});left++;}}}vector<vector<int>> ret;for(auto it : res){ret.push_back(it);}return ret;}
};

离谱……………………

对于去重的方法有进一步优化

 将c从右向左固定:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();vector<vector<int>> ret;sort(nums.begin(), nums.end());    1、排序for(int i = n-1; i > 1; ){int c = nums[i];int temp = 0-c;int left = 0, right = i-1;while(left < right)  2、此处使用双指针思想{if(nums[left] + nums[right] < temp)left++;else if(nums[left] + nums[right] > temp)right--;else{ret.push_back({nums[left], nums[right], c});int flag = nums[left++];while(left<right && nums[left] == flag)   left++;        3、对于去重操作的优化①flag = nums[right--];while(left<right && nums[right] == flag)right--;}}i--;                       4、去重的优化②while(i>1 && nums[i+1] == nums[i]) // 把whlie写错成if调试半天才发现i--;}return ret;}
};

将c从左向右固定

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());    // 1、排序vector<vector<int>> ret;for(int i = 0; i < n; ){if(nums[i] > 0) break;    // 2、作一个小优化,如果左边数大于零则无法满足和为0int left = i+1, right = n-1;int target = -nums[i];while(left < right)        // 3、双指针进行寻找{int sum = nums[left] + nums[right];if(sum < target)    left++;else if(sum > target)   right--;else{ret.push_back({nums[i], nums[left++], nums[right--]});while(left < right && nums[left] == nums[left-1])left++; // 当left位置重复时,left后移while(left < right && nums[right] == nums[right+1])right--; // 当right位置重复时,right左移}}i++;while(i < n && nums[i]==nums[i-1])i++;}return ret;}
};

相关文章:

对撞双指针(七)三数之和

15. 三数之和 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可以包含重复的三元组…...

【Ubuntu24.04】服务部署(虚拟机)

目录 0 背景1 安装虚拟机1.1 下载虚拟机软件1.2 安装虚拟机软件1.2 安装虚拟电脑 2 配置虚拟机2.1 配置虚拟机网络及运行初始化脚本2.2 配置服务运行环境2.2.1 安装并配置JDK172.2.2 安装并配置MySQL8.42.2.3 安装并配置Redis 3 部署服务4 总结 0 背景 你的服务部署在了你的计算…...

timm库加载的模型可视化

在深度学习中&#xff0c;模型的可视化有助于了解模型的结构和层级关系。以下是几种方式来可视化使用 timm 库加载的模型&#xff1a; 打印模型结构 torch.nn.Module 的子类&#xff08;包括 timm 的模型&#xff09;可以通过 print() 查看其结构&#xff1a;import timm# 加…...

服务限流、降级、熔断-SpringCloud

本文所使用的组件&#xff1a;Nacos&#xff08;服务中心和注册中心&#xff09;、OpenFeign&#xff08;服务调用&#xff09;、Sentinel&#xff08;限流、降级&#xff09;、Hystrix&#xff08;熔断&#xff09; 项目结构&#xff1a; service-provider&#xff1a;提供服…...

2024最新YT-DLP使用demo网页端渲染

2024最新YT-DLP使用demo网页端渲染 前提摘要1.使用python的fastapi库和jinjia2库进行前端渲染2.代码实现1&#xff09;目录结构2&#xff09;代码style.cssindex.htmlresult.htmlmain.pyrun.py 3&#xff09;运行测试命令端运行 3.项目下载地址 前提摘要 2024最新python使用yt…...

《第十部分》1.STM32之通信接口《精讲》之IIC通信---介绍

经过近一周的USART学习&#xff0c;我深刻体会到通信对单片机的重要性。它就像人类的手脚和大脑&#xff0c;只有掌握了通信技术&#xff0c;单片机才能与外界交互&#xff0c;展现出丰富多彩的功能&#xff0c;变得更加强大和实用。 单片机最基础的“语言”是二进制。可惜&am…...

wireshark使用lua解析自定义协议

wireshark解析自定义协议 1.自定义的lua放入路径2.修改init.lua2.1 开启lua2.2 init.lua文件最后加入自己的lua文件位置&#xff0c;这里需要确保与自己的文件名相同 3.编写lua4.编写c抓包5.wireshark添加自定义协议如何加调试信息 1.自定义的lua放入路径 一般是自己软件的安装…...

(Keil)MDK-ARM各种优化选项详细说明、实际应用及拓展内容

参考 MDK-ARM各种优化选项详细说明、实际应用及拓展内容 本文围绕MDK-ARM优化选项,以及相关拓展知识(微库、实际应用、调试)进行讲述,希望对你今后开发项目有所帮助。 1 总述 我们所指的优化,主要两方面: 1.代码大小(Size) 2.代码性能(运行时间) 在MDK-ARM中,优…...

Qt实现可拖拽的矩形

之前项目上需要用Qt来绘制可拖拽改变形状的矩形。看了Qt Graphics相关的内容&#xff0c;虽然对Qt怎么添加图元的有了些了解&#xff0c;但是具体如何实现拖拽效果&#xff0c;一时也没有什么好的想法。还好网上有人分享的例子&#xff0c;很受启发。后来又回顾了一下这部分的代…...

CentOS:A服务器主动给B服务器推送(上传),B服务器下载A服务器文件(下载)

Linux:常识(bash: ip command not found )_bash: ip: command not found-CSDN博客 rsync 中断后先判断程序是否自动重连:ps aux | grep rsync 查看目录/文件是否被使用(查询线程占用):lsof /usr/local/bin/mongodump/.B_database1.6uRCTp 场景:MongoDB中集合非常大需要…...

Oracle 执行计划查看方法汇总及优劣对比

在 Oracle 数据库中&#xff0c;查看执行计划是优化 SQL 语句性能的重要工具。以下是几种常用的查看执行计划的方法及其优劣比较&#xff1a; 1. 使用 EXPLAIN PLAN FOR 和 DBMS_XPLAN.DISPLAY 方法 执行 EXPLAIN PLAN FOR 语句&#xff1a; EXPLAIN PLAN FOR SELECT * FROM …...

TCL大数据面试题及参考答案

Mysql 索引失效的场景 对索引列进行运算或使用函数:当在索引列上进行数学运算、函数操作等,索引可能失效。例如,在存储年龄的列上建立了索引,若查询语句是 “SELECT * FROM table WHERE age + 1 = 20”,这里对索引列 age 进行了加法运算,数据库会放弃使用索引而进行全表扫…...

九、FOC原理详解

1、FOC简介 FOC&#xff08;field-oriented control&#xff09;为磁场定向控制&#xff0c;又称为矢量控制&#xff08;vectorcontrol&#xff09;&#xff0c;是目前无刷直流电机&#xff08;BLDC&#xff09;和永磁同步电机&#xff08;PMSM&#xff09;高效控制的最佳选择…...

vue页面成绩案例(for渲染表格/删除/添加/统计总分/平均分/不及格显红色/输入内容去首尾空格trim/输入内容转数字number)

1.使用v-if 和v-else 完成<tbody>标签的条件渲染 2.v-for完成列表渲染 3.:class完成分数标红的条件控制 删哪个就传哪个的id&#xff0c;基于这个id去过滤掉相同id的项&#xff0c;把剩下的项返回 a标签的默认点击事件会跳转 这里要禁止默认事件 即使用click.provent 就…...

STM32编程小工具FlyMcu和STLINK Utility 《通俗易懂》破解

FlyMcu FlyMcu 模拟仿真软件是一款用于 STM32 芯片 ISP 串口烧录程序的专用工具&#xff0c;免费&#xff0c;且较为非常容易下手&#xff0c;好用便捷。 注意&#xff1a;STM32 芯片的 ISP 下载&#xff0c;只能使用串口1&#xff08;USART1&#xff09;&#xff0c;对应的串口…...

Centos使用docker搭建Graylog日志平台

日志管理系统有很多&#xff0c;比如ELK,Graylog&#xff0c;LokiGrafanaPromtail 适用场景&#xff1a; 1.如果需求复杂&#xff0c;服务器资源不受限制&#xff0c;推荐使用ELK&#xff08;Logstash Elasticsearch Kibana&#xff09;方案&#xff1b; 2.如果需求仅是将…...

自定义 Kafka 脚本 kf-use.sh 的解析与功能与应用示例

Kafka&#xff1a;分布式消息系统的核心原理与安装部署-CSDN博客 自定义 Kafka 脚本 kf-use.sh 的解析与功能与应用示例-CSDN博客 Kafka 生产者全面解析&#xff1a;从基础原理到高级实践-CSDN博客 Kafka 生产者优化与数据处理经验-CSDN博客 Kafka 工作流程解析&#xff1a…...

【SQL】【数据库】语句翻译例题

SQL自然语言到SQL翻译知识点 以下是将自然语言转化为SQL语句的所有相关知识点&#xff0c;分门别类详细列出&#xff0c;并结合技巧说明。 1. 数据库操作 创建数据库 自然语言&#xff1a;创建一个名为“TestDB”的数据库。 CREATE DATABASE TestDB;技巧&#xff1a;识别**“创…...

linux基本命令2

7. 文件查找和搜索 (继续) find — 查找文件 find /path/to/search -name "file_name" # 根据名称查找文件 find /path/to/search -type f # 查找所有普通文件 find /path/to/search -type d # 查找所有目录 find /path/to/search -name "*.txt" # 查找…...

Spring Boot项目集成Redisson 原始依赖与 Spring Boot Starter 的流程

Redisson 是一个高性能的 Java Redis 客户端&#xff0c;提供了丰富的分布式工具集&#xff0c;如分布式锁、Map、Queue 等&#xff0c;帮助开发者简化 Redis 的操作。在集成 Redisson 到项目时&#xff0c;开发者通常有两种选择&#xff1a; 使用 Redisson 原始依赖。使用 Re…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...