leetcode面试 150题之 三数之和 复刷日记

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

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

题目重点  不重复的三数和为0

这里如果是暴力做法也就是三层for循环去暴力遍历

我先想到的是双指针固定两个数然后二分找第三个数(有点想当然)

这里代码只能处理一半的数据 当遇到  -4 -2 -2 0 2 2 4时就漏情况了,而且处理起来非常麻烦

我的逻辑是排序后左右指针分别确定一个数,当左右指针之间没有元素或者相乘同号则结束查找,否则去寻找三个数 

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int l=0,r=n-1;
        vector<vector<int>> tar;
        while(l<r-1&&nums[l]*nums[r]<=0)
        {
            int value=nums[l]+nums[r];
            if((l>=1&&nums[l]==nums[l-1])||(value+nums[r]<0)){l++;continue;};
            if((r<n-1&&nums[r]==nums[r+1])||(value+nums[l]>0)){r--;continue;};
            int left=l+1,right=r,mid=0;
            while(left<right)
            {
                mid=(left+right)/2;
                if(nums[mid]+value==0)
                {
                    tar.push_back({nums[l],nums[mid],nums[r]});
                    break;
                }
                else if(nums[mid]+value>0)  right=mid;
                else left=mid+1;
            }
            if(value>0) r--;
            else l++;
        }
        return tar;
    }
};

 

 

然后我尝试只固定一个值,因为上面的 -4 -2 -2 0 2 2 4 中就是因为我锁定l,r导致无论是l++,还是r--都会丢掉一个解
 这里我们选择了一个值后 再去通过双指针找与该值到和为0的二元组,这里的去重就简单了,已经固定了一个值,这里的二元组只要有一个和之前的相等则指针相应的++或者--直到找不到二元组和固定值为相反数为止

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> tar;
        for(int i=0;i<nums.size()-2;i++)
        {
            int l=i+1,r=nums.size()-1;
            if(i>=1&&nums[i]==nums[i-1]) continue;
            while(l<r)
            {
                int value=nums[l]+nums[r]+nums[i];
                if(value>0) r--;
                else if(value<0) l++;
                else
                {
                    tar.push_back({nums[i],nums[l],nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) l++; //去重
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return tar;
    }
};

这里的时间复复杂度为O(n*n) 我以为我的方法能O(nlogn)实现,想当然了也是

 

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

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

相关文章

git根据远程分支创建本地新分支

比如我当前本地仓库有4个 remote 仓库&#xff0c;我希望根据其中的一个 <remote>/<branch> 创建本地分支&#xff1a; 先使用 github fetch <remote> 拉取 <remote> 的分支信息&#xff0c;然后在 git checkout -b 创建新分支时使用 -t <remote>…

r-and-r——提高长文本质量保证任务的准确性重新提示和上下文搜索的新方法可减轻大规模语言模型中的迷失在中间现象

概述 随着大规模语言模型的兴起&#xff0c;自然语言处理领域取得了重大发展。这些创新的模型允许用户通过输入简单的 "提示 "文本来执行各种任务。然而&#xff0c;众所周知&#xff0c;在问题解答&#xff08;QA&#xff09;任务中&#xff0c;用户在处理长文本时…

Redis 概 述 和 安 装

安 装 r e d i s: 1. 下 载 r e dis h t t p s : / / d o w n l o a d . r e d i s . i o / r e l e a s e s / 2. 将 redis 安装包拷贝到 /opt/ 目录 3. 解压 tar -zvxf redis-6.2.1.tar.gz 4. 安装gcc yum install gcc 5. 进入目录 cd redis-6.2.1 6. 编译 make …

Android 项目依赖库无法找到的解决方案

目录 错误信息解析 解决方案 1. 检查依赖版本 2. 检查 Maven 仓库配置 3. 强制刷新 Gradle 缓存 4. 检查网络连接 5. 手动下载依赖 总结 相关推荐 最近&#xff0c;我在编译一个 Android 老项目时遇到了一个问题&#xff0c;错误信息显示无法找到 com.gyf.immersionba…

北航软件算法C4--图部分

C4上级图部分 TOPO!步骤代码段TOPO排序部分 完整代码 简单的图图题目描述输入输出样例步骤代码段开辟vector容器作为dist二维数组初始化调用Floyd算法查询 完整代码 负环题目描述输入输出样例步骤代码段全局变量定义spfa1函数用于判断是否有负环spfa2用于记录每个点到1号点的距…

ks 小程序sig3

前言 搞了app版的快手之后 &#xff08;被风控麻了&#xff09; 于是试下vx小程序版的 抓包调试 小程序抓包问题 网上很多教程&#xff0c; github也有开源的工具代码 自行搜索 因为我们需要调试代码&#xff0c;所以就用了下开源的工具 &#xff08;可以用chrome的F12功能&a…

docker:docker: Get https://registry-1.docker.io/v2/: net/http: request canceled

无数次的拉镜像让人崩溃&#xff1a; rootnode11:~/ragflow/docker# more rag.sh #export HTTP_PROXYhttp://192.168.207.127:7890 #export HTTPS_PROXYhttp://192.168.207.127:7890 #export NO_PROXYlocalhost,127.0.0.1,.aliyun.com docker compose -f docker-compose-gpu-C…

基于java Springboot高校失物招领平台

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…

菜鸟驿站二维码/一维码 取件识别功能

特别注意需要引入 库文 ZXing 可跳转&#xff1a; 记录【WinForm】C#学习使用ZXing.Net生成条码过程_c# zxing-CSDN博客 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Net.…

使用WebRTC实现点对点实时音视频通信的技术详解

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用WebRTC实现点对点实时音视频通信的技术详解 使用WebRTC实现点对点实时音视频通信的技术详解 使用WebRTC实现点对点实时音视频…

执行flink sql连接clickhouse库

手把手教学&#xff0c;flink connector打通clickhouse大数据库&#xff0c;通过下发flink sql&#xff0c;来使用ck。 组件版本jdk1.8flink1.17.2clickhouse23.12.2.59 1.背景 flink官方不支持clickhouse连接器&#xff0c;工作中难免会用到。 2.方案 利用GitHub大佬提供…

力扣(leetcode)题目总结——辅助栈篇

leetcode 经典题分类 链表数组字符串哈希表二分法双指针滑动窗口递归/回溯动态规划二叉树辅助栈 本系列专栏&#xff1a;点击进入 leetcode题目分类 关注走一波 前言&#xff1a;本系列文章初衷是为了按类别整理出力扣&#xff08;leetcode&#xff09;最经典题目&#xff0c…

基于Java Springboot宠物猫售卖管理系统

一、作品包含 源码数据库全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据库&#xff1a;…

Windows docker下载minio出现“Using default tag: latestError response from daemon”

Windows docker下载minio出现 Using default tag: latest Error response from daemon: Get "https://registry-1.docker.io/v2/": context deadline exceeded 此类情况&#xff0c;一般为镜像地址问题。 {"registry-mirrors": ["https://docker.re…

数据结构查找-哈希表(开发地址法+线性探测法)+(创建+查找+删除代码)+(C语言代码)

#include<stdlib.h> #include<stdio.h> #include<stdbool.h> #define NULLKEY -1//单元为空 #define DELKEY -2//单元内容被删除 #define M 20 typedef struct {int key;//关键字int count;//统计哈希冲突探测次数 }HashTable; //插入到哈希表 void InsertHT…

视频直播5G CPE解决方案:ZX7981PG/ZX7981PMWIFI6网络覆盖

方案背景 视频直播蓬勃发展的当下&#xff0c;传统直播网络联网方式的局限性越来越明显。目前传统直播的局限性主要集中在以下几个方面&#xff1a; 传统直播间网络架构条件有限&#xff0c;可连接WIFI数量少&#xff0c;多终端同时直播难以维持&#xff1b;目前4G网络带宽有限…

【电子设计】按键LED控制与FreeRTOS

1. 安装Keilv5 打开野火资料,寻找软件包 解压后得到的信息 百度网盘 请输入提取码 提取码:gfpp 安装526或者533版本都可以 下载需要的 F1、F4、F7、H7 名字的 DFP pack 芯片包 安装完 keil 后直接双击安装 注册操作,解压注册文件夹后根据里面的图示步骤操作 打开说明 STM…

vue3【实战】切换白天黑夜(暗黑模式)【组件封装】DarkMode.vue

效果预览 原理解析 切换为暗黑模式时&#xff0c;会在 html 标签上添加样式类 dark导入 ElementPlus 的暗黑模式样式后&#xff0c; ElementPlus 组件会自动响应暗黑模式自定义组件需用 UnoCSS 的 dark: 语法自定义暗黑模式的样式 代码实现 技术方案 vue3 vite ElementPlus …

基于单片机的多功能环保宠物窝设计

本设计基于单片机设计的多功能环保宠物窝&#xff0c;利用温湿度传感器、压力传感模块、气味传感模块、红外测温传感器、通信模块、显示模块、清扫部件等&#xff0c;使其能够实现自动检测并调节温湿度、补充宠物食物、检测宠物体温健康并出现异常时进行报警、自动清扫消毒宠物…

MySql结合element-plus pagination的分页查询

实现效果如下&#xff1a; 重点&#xff1a;使用mysql查询的limit和offset 原生SQL写法&#xff1a; select c.id as deptid,c.name as department,position,a.name staffname,2024-11 as shijian ,CASE WHEN b.shijian IS NULL THEN no ELSE yes END AS submit from fa_wecom…