【刷题笔记】--两数之和Ⅳ,从二叉树中找出两数之和

法一:深度搜索+中序遍历+双指针
思路:通过中序遍历二叉树得到一个递增的数列,再在这个递增的二叉树中找到这两数。
主要学到双指针这个方法。
对于一般数列,我们要找到两数满足其之和等于目标数,我们一般会进行暴力,即两重循环:
for(i=0;i<length;i++){for(j=i+1;j<length;j++){}
}
对于暴力,我们要把下图的空白格全都依次检验,贼费时间。

而如果设置双指针,对应 i 和 j ,分别指向数组的头和尾。
如果a[0]+a[7]<target,说明a[0]+a[1],a[0]+a[2],a[0]+a[3],a[0]+a[4].....全都不满足,我们就可以直接把a[0]+的所有数给全部排除。 即把i=0时的那一排全排除了。
如果a[0]+a[7]>target,说明a[1]+a[7],a[2]+a[7],a[3]+a[7]......全不满足,我们就可以把j=7的那一列全排除了。
总结就是 i 是指向数组头的指针,如果i 右移,则删排,j 是指向数组尾的指针,如果j 左移,则删列。
这是缩减搜索空间的思想。
题解参考一张图告诉你 O(n) 的双指针解法的本质原理(C++/Java) - 两数之和 II - 输入有序数组 - 力扣(LeetCode)
代码:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
void inorderTraversal(const struct TreeNode* node, int* vec, int* pos) {if (node == NULL) {return;}inorderTraversal(node->left, vec, pos);vec[(*pos)++] = node->val;inorderTraversal(node->right, vec, pos);
}bool findTarget(struct TreeNode* root, int k) {int * vec = (int *)malloc(sizeof(int) * 10000);int pos = 0;inorderTraversal(root, vec, &pos);int left = 0, right = pos - 1;while (left < right) {if (vec[left] + vec[right] == k) {return true;}if (vec[left] + vec[right] < k) {left++;} else {right--;}}free(vec);return false;
}
相关文章:
【刷题笔记】--两数之和Ⅳ,从二叉树中找出两数之和
法一:深度搜索中序遍历双指针 思路:通过中序遍历二叉树得到一个递增的数列,再在这个递增的二叉树中找到这两数。 主要学到双指针这个方法。 对于一般数列,我们要找到两数满足其之和等于目标数,我们一般会进行暴力&a…...
浏览器渲染原理JavaScript V8引擎
浏览器渲染原理 前言 在我们面试过程中,面试官经常会问到这么一个问题,那就是从在浏览器地址栏中输入URL到页面显示,浏览器到底发生了什么? 浏览器内有哪些进程,这些进程都有些什么作用;浏览器地址输入U…...
在TheSandbox 的「BOYS PLANET」元宇宙中与你的男孩们见面吧!
世界各的男孩们成为 K-Pop 男团的旅程。 Mnet 的全球项目 BOYS PLANET 终于在 2 月 2 日首次亮相! The Sandbox 与 CJ ENM 合作,于 2 月 6 日晚上 10 点开始举办两个基于 BOYS PLANET 生存节目的虚拟体验:BOYS PLANET:BOYS LAND 和…...
数据结构与算法:java对象的比较
1.基本类型的比较 在Java中,基本类型的对象可以直接比较大小。 public class TestCompare {public static void main(String[] args) {int a 10;int b 20;System.out.println(a > b);System.out.println(a < b);System.out.println(a b);char c1 A;char…...
python(16)--类
一、类的基本操作1.定义一个类格式:class Classname( ):内容💎鄙人目前还是一名学生,最熟悉的也就是学校了,所以就以学校为例子来建立一个类吧class School():headline"帝国理工大学"def schoolmotto(self):…...
CNI 网络流量分析(七)Calico 介绍与原理(二)
文章目录CNI 网络流量分析(七)Calico 介绍与原理(二)CNIIPAM指定 IP指定非 IPAM IPCNI 网络流量分析(七)Calico 介绍与原理(二) CNI 支持多种 datapath,默认是 linuxDa…...
API安全的最大威胁:三体攻击
最近《三体》火的一塌糊涂,动画片、电视剧和书都受到了大家的喜爱。在API安全上,最近也发现了三体攻击。 当然了,肯定是不来自于三体人的攻击,这里的三体攻击指的是(trinity,也称三位一体攻击),是一个新的攻击手法。具体的情况老李也找到了相关的介绍,下面就分享给大…...
分布式事务解决方案——TCC
TCC是Try、Confirm、Cancel三个词语的缩写,TCC要求每个分支事务实现三个操作:预处理Try、确认Confirm、撤销Cancel。1、Try 阶段是做业务检查(一致性)及资源预留(隔离),此阶段仅是一个初步操作,它和后续的Confirm一起才能真正构成…...
ITSS认证分为几个级别,哪个级别最高
一、什么是ITSS ITSS( 信息技术服务标准,简称ITSS)是国内第一套成体系和综合配套的信息技术服务标准库,全面规范了IT服务产品及其组成要素,用于指导实施标准化和可信赖的IT服务。 ITSS是在工业和信息化部、国家标准化管理委员会的联合指导下…...
ZigBee案例笔记 - USART
文章目录1.串行通信接口简述2.串行通信接口寄存器U0CSR (0x86) -USART 0 控制和状态U0UCR (0xC4)–USART 0 UART 控制U0GCR (0xC5)–USART 0 通用控制U0BUF (0xC1) – USART 0 接收/传送数据缓存U0BAUD (0xC2) – USART 0 波特率控制3.设置串行通信接口比特率控制寄存器4.外设I…...
java | 基于Redis的分布式锁实现①
前言 首先,为了确保分布式锁可用,我们至少要确保锁的实现同时满足以下四个条件: 互斥性。在任意时刻,只有一个客户端能持有锁。不会发生死锁。即使有一个客户端在持有锁的期间崩溃而没有主动解锁,也能保证后续其他客户…...
十六、基于FPGA的CRC校验设计实现
1,CRC校验循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术,主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的…...
2022爱分析 · DataOps厂商全景报告 | 爱分析报告
报告编委 李喆 爱分析合伙人&首席分析师 廖耘加 爱分析分析师 目录 1. 研究范围定义 2. 市场洞察 3. 厂商全景地图 4. 市场分析与厂商评估 5. 入选厂商列表 1. 研究范围定义 研究范围 在后疫情时代,以数据分析为代表的数据消费场景日益丰富&…...
京东前端react面试题及答案
useEffect 与 useLayoutEffect 的区别 (1)共同点 运用效果: useEffect 与 useLayoutEffect 两者都是用于处理副作用,这些副作用包括改变 DOM、设置订阅、操作定时器等。在函数组件内部操作副作用是不被允许的,所以需…...
TongWeb8数据源相关问题
问题一:数据源连接不足当TongWeb数据源连接用完时,除了监控中看到连接占用高以外,日志中会有如下提示信息。2023-02-14 10:24:43 [WARN] - com.tongweb.web.jdbc.pool.PoolExhaustedException: [TW-0.0.0.0-8088-3] Timeout: Pool empty. Una…...
关于最近大热的AI,你怎么看?
AI人工智能,相信大家都不陌生,也都接触过不少。但是最近小编在网上冲浪的时候发现各大媒体又掀起了一阵AI热潮,AI不是很常见了吗?是又有什么新的发展吗? 带着强烈的好奇心,我在地铁上读完了一篇关于Chatgp…...
25.架构和软件产品线
文章目录25 Architecture and Software Product Lines架构和软件产品线25.1 An Example of Product Line Variability 产品线可变性的一个例子25.2 What Makes a Software Product Line Work? 软件产品线的工作原理是什么?25.3 Product Line Scope 产品线范围25.4 …...
Seata-server 源码学习(一)
Seata源码学习引入 学习了Seata的应用以后,我们从这开始要开始分析Seata的源码相关内容 源码下载 官方地址:https://seata.io/zh-cn/blog/download.html 通过idea打开seata-1.4.2版本的源码 回顾AT模式 其实在之前的应用课程中,我们已经用…...
2023新华为OD机试题 - 斗地主(JavaScript)
斗地主 题目 斗地主起源于湖北十堰房县, 据传是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的, 如今已风靡整个中国,并流行于互联网上 牌型: 单顺,又称顺子,最少5张牌,最多12张牌(3...A),不能有2, 也不能有大小王,不计花色 例如:3-4-5-7-8,7-8-9-1…...
素数相关(结合回文数,合数)线性筛素数(欧拉筛法)Euler【算法模板笔记】
一、朴素筛法(埃拉托斯特尼筛法)Eratosthenes 筛法(埃拉托斯特尼筛法,简称埃氏筛法)时间复杂度是O(nloglogn)不常用,被欧拉筛代替,略二、线性筛素数(欧拉筛法)简介线性筛…...
Cherry Studio快速上手:从零部署到实战避坑指南
Cherry Studio快速上手:从零部署到实战避坑指南 【免费下载链接】cherry-studio 🍒 Cherry Studio is a desktop client that supports for multiple LLM providers. Support deepseek-r1 项目地址: https://gitcode.com/GitHub_Trending/ch/cherry-st…...
突破macOS无损音质瓶颈:LosslessSwitcher实现音频采样率智能切换
突破macOS无损音质瓶颈:LosslessSwitcher实现音频采样率智能切换 【免费下载链接】LosslessSwitcher Automated Apple Music Lossless Sample Rate Switching for Audio Devices on Macs. 项目地址: https://gitcode.com/gh_mirrors/lo/LosslessSwitcher 副标…...
WinUtil终极指南:10分钟掌握Windows系统管理与优化工具
WinUtil终极指南:10分钟掌握Windows系统管理与优化工具 【免费下载链接】winutil Chris Titus Techs Windows Utility - Install Programs, Tweaks, Fixes, and Updates 项目地址: https://gitcode.com/GitHub_Trending/wi/winutil WinUtil是一款强大的Windo…...
CodeQuery:打破代码理解的次元壁
CodeQuery:打破代码理解的次元壁 【免费下载链接】codequery A code-understanding, code-browsing or code-search tool. This is a tool to index, then query or search C, C, Java, Python, Ruby, Go and Javascript source code. It builds upon the databases…...
从8小时到15分钟:feishu-doc-export如何重构飞书文档管理流程
从8小时到15分钟:feishu-doc-export如何重构飞书文档管理流程 【免费下载链接】feishu-doc-export 项目地址: https://gitcode.com/gh_mirrors/fe/feishu-doc-export feishu-doc-export是一款基于.NET框架开发的飞书文档批量导出工具,通过封装飞…...
5大优势:邱锡鹏《神经网络与深度学习》如何帮新手系统掌握AI核心技术
5大优势:邱锡鹏《神经网络与深度学习》如何帮新手系统掌握AI核心技术 【免费下载链接】nndl.github.io 《神经网络与深度学习》 邱锡鹏著 Neural Network and Deep Learning 项目地址: https://gitcode.com/GitHub_Trending/nn/nndl.github.io 神经网络与深…...
Lightpanda无头浏览器:11倍性能提升的自动化革命指南
Lightpanda无头浏览器:11倍性能提升的自动化革命指南 【免费下载链接】browser The open-source browser made for headless usage 项目地址: https://gitcode.com/GitHub_Trending/browser32/browser 你是否厌倦了传统浏览器在自动化任务中消耗大量内存&…...
Android网络请求库终极对决:xUtils3 vs Retrofit 完整指南
Android网络请求库终极对决:xUtils3 vs Retrofit 完整指南 【免费下载链接】xUtils3 Android orm, bitmap, http, view inject... 项目地址: https://gitcode.com/gh_mirrors/xu/xUtils3 在Android开发的世界中,网络请求是每个应用的核心功能之一…...
如何利用gs-quant构建专业量化金融分析系统
如何利用gs-quant构建专业量化金融分析系统 【免费下载链接】gs-quant 用于量化金融的Python工具包。 项目地址: https://gitcode.com/GitHub_Trending/gs/gs-quant 在现代金融市场中,量化分析已成为投资决策的核心驱动力。随着市场复杂度提升,金…...
PyTorch 2.8镜像问题解决:常见CUDA内存不足、加载慢等故障排查指南
PyTorch 2.8镜像问题解决:常见CUDA内存不足、加载慢等故障排查指南 你是不是也遇到过这样的场景?在云端启动了一个全新的PyTorch 2.8镜像,准备大展身手训练模型,结果刚跑几行代码就弹出“CUDA out of memory”的红色警告。或者&a…...
