新闻详情

新闻详情

首页 / 资讯中心 / 详情

问的是最少拿几次,答案在最长的那一段

发布时间:2026/11/16 16:56:29来源:尧图网络
问的是最少拿几次,答案在最长的那一段
一个数组每次从最左边或最右边拿走一个数字拿走的加起来要正好等于给定的目标值问最少拿几次。正面去数每一次该拿左边还是右边路子很绕。把这道题反过来看剩下的只是一段连续区间的事。这篇要讲的就是怎么把那段区间找出来。先把题目翻译成人话为了讲得顺后面换个说法把数组里每个数字看成一块饼干把移除看成拿走。规则一个字没改只是叫法变了。一排饼干每块上面写着重量1 2 3每次只能拿走最左边或最右边那一块拿走的重量加起来要正好等于x。问最少拿几次。凑不出来就返回 -1。正面去数能做但很绕最直接的想法是逐个位置做决定拿左边还是拿右边。拿两次有 4 条路拿三次有 8 条拿十次有 1024 条规律是 2 的 k 次方。这么一条条试下去时间就不够用了。不过这个数字得说准。它数的是带顺序的路径数先左后右和先右后左在题目看来是同一个结果所以这个 2 的 k 次方里有一部分是重复的。真正要定的其实只有两个数左边拿走几个记作L右边拿走几个记作R。数组长度记作n满足L R n的L、R组合有O(n²)个。所以正面也做得出来。只是要额外小心左右两边别重复拿还要在几个都行的方案里挑次数最小的那个写起来啰嗦。反过来数看留下多少先看拿走的和留下的。拿走的 留下的 全部既然总共就这么多留下的重量一定是留下的重量 全部重量 - x再看一层关系拿得越少留下的越多拿得越多留下的越少。所以要拿的次数最少就是让留下的最多。而留下的那几块是两头拿完之后剩下的一定是中间连着的一段。如果一块都不留那留下的长度就是 0。题目到这里就变成一句话找出连着的几块饼干它们重量加起来正好等于全部重量 - x要求越长越好。设最长能留maxLen块答案就是n - maxLen。怎么找连着的、重量刚好等于某值的一段用前缀和。再准备一本记事本专门记下每个累加和对应的位置。先把从头加到某一个位置的累加和列出来位置 -1 0 1 2 累加和 0 1 3 6位置 -1 是虚拟的代表还没开始加。有了这张表任意一段[k, i]的重量就等于位置 i 的累加和 - 位置 k-1 的累加和想让它等于全部重量 - x下面把这个目标值记作target移项就得到位置 k-1 的累加和 位置 i 的累加和 - target所以每走到一个位置就拿当前累加和 - target去记事本里翻。翻到了说明那一段就是从翻到的位置开始一直加到现在这个位置重量正好是target。这一段的长度就是当前位置减去翻到的位置。记事本记的是累加和 → 它最早出现的位置。非要记最早的那个是因为起点越靠前这一段越长而我们要的就是最长。为什么开头要先放一个 0记事本开头先放一条累加和 0 → 出现在位置 -1-1是个虚拟位置它在数组第一个元素位置 0的前面代表还什么都没累加的状态那时候累加和就是 0。从头开始的段全都要靠它。算一段[k, i]要用两个累加和相减。当k 0时要减掉的那个累加和就是位置 -1 上的 0。少了这条那个 0 就翻不到从头开始的段全都查不出来。看一个具体例子nums [1, 2, 3], x 3 total 6 target total - x 3 ← 要留下的重量预期答案从右边拿走 3一次搞定剩下[1, 2]重量正好是 3所以最少 1 次。记事本开头{0 → -1}走到位置 0累加和 1记事本记下1 → 0。查1 - 3 -2记事本里没有跳过。走到位置 1累加和 3记事本记下3 → 1。查3 - 3 0记事本里有记的是位置 -1。长度 1 - (-1) 2这一段就是[1, 2]最长记录更新为 2。走到位置 2累加和 6记事本记下6 → 2。查6 - 3 3记事本里有记的是位置 1。长度 2 - 1 1这一段是[3]没超过 2不更新。最长的一段长度是 2答案 3 - 2 1。翻译成 Java 代码classSolution{publicintminOperations(int[]nums,intx){// 全部重量inttotalArrays.stream(nums).sum();// 要留下的重量 全部重量 - xinttargettotal-x;// 记事本累加和 - 这个累加和最早出现在哪个位置MapInteger,IntegerfirstIndexnewHashMap();// 位置 -1 是个虚拟位置在数组第一个元素前面累加和是 0firstIndex.put(0,-1);intsum0;// 走到这个位置为止的累加和intmaxLen-1;// 留下的最长一段的长度for(inti0;inums.length;i){sumnums[i];// 同一个累加和只记最早那次后来的不覆盖firstIndex.putIfAbsent(sum,i);// 要找的那段它起点之前的累加和是 sum - targetintneedsum-target;if(firstIndex.containsKey(need)){maxLenMath.max(maxLen,i-firstIndex.get(need));}}// 一段都凑不出来就返回 -1否则答案 总块数 - 留下的最长一段returnmaxLen-1?-1:nums.length-maxLen;}}代码大白话total全部重量target要留下的重量等于全部重量减去xfirstIndex记事本累加和 → 最早出现的位置put(0, -1)在数组前面放一个虚拟位置撑起从头开始的那些段putIfAbsent(sum, i)同一个累加和只记最早那次段才能最长sum - target就是当前累加和 - target拿去查记事本i - firstIndex.get(need)这一段的长度nums.length - maxLen留下的最多拿走的就最少C 版同一套思路C 用unordered_map记累加和把只记最早那次写成emplace。classSolution{public:intminOperations(vectorintnums,intx){inttotal0;for(intv:nums)totalv;// 要留下的重量 全部重量 - xinttargettotal-x;// 记事本累加和 - 这个累加和最早出现在哪个位置unordered_mapint,intfirstIndex;firstIndex[0]-1;intsum0,maxLen-1;for(inti0;i(int)nums.size();i){sumnums[i];// emplace 遇到已有的 key 不覆盖正好只留最早那次firstIndex.emplace(sum,i);intneedsum-target;autoitfirstIndex.find(need);if(it!firstIndex.end()){maxLenmax(maxLen,i-it-second);}}returnmaxLen-1?-1:(int)nums.size()-maxLen;}};Python 版同一套思路Python 用字典记累加和判存在用in取位置直接用下标代码最短。classSolution:defminOperations(self,nums:list[int],x:int)-int:totalsum(nums)targettotal-x first_index{0:-1}# 记事本累加和 - 最早出现的位置cur0max_len-1fori,vinenumerate(nums):curv# 同一个累加和只记最早那次后来的不动它ifcurnotinfirst_index:first_index[cur]i needcur-targetifneedinfirst_index:max_lenmax(max_len,i-first_index[need])return-1ifmax_len-1elselen(nums)-max_len几处容易写错的地方put(0, -1)不能少少了这一条[1, 2]这种从头开始的段就查不出来。还是[1, 2, 3]那个例子能留下的最长一段只剩 1 块答案就从3 - 2 1变成3 - 1 2。记事本只记最早的位置写成每次覆盖成最新位置段会越算越短。Java 的putIfAbsent和 C 的emplace就是干这件事的。返回的是n - maxLenmaxLen记的是留下的长度题目问的是拿走的次数。两者加起来才是全部。x正好等于全部重量时答案是n这时target是 0对应的情况是一块都不留留下的长度是 0。不用为它单独写判断循环里每一个位置都是先把累加和写进记事本再查need正好等于刚写进去的当前累加和查到的是它自己长度是 0最后返回n。x比全部重量还大时无解target变成负数。题目里的数字都是正数任意一段的重量都不可能是负数。记事本里永远查不到maxLen保持 -1函数自动返回 -1。开销有多大只扫一遍数组每个位置查一次记事本。时间O(n)空间O(n)记事本最多存下n 1个累加和。收个尾这道题最关键的地方就是把问题反过来看。同一件事正面去算怎么拿走得先定左右各拿多少还要保证两边别重复拿最后再比一比谁拿得更少。反过来算怎么留下剩下的是一段连续区间要满足的条件只剩一条重量。这一换要防的坑少了一大半。前缀和配一本记事本是找连续区间和恰好等于某值的标准搭配。区间和、子数组和这一类的题很多都是它的变形。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/15 4:54:16

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/15 2:04:12

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/14 10:11:15

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/16 6:47:19

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/14 16:35:50

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/15 4:06:36

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉