一个数组每次从最左边或最右边拿走一个数字拿走的加起来要正好等于给定的目标值问最少拿几次。正面去数每一次该拿左边还是右边路子很绕。把这道题反过来看剩下的只是一段连续区间的事。这篇要讲的就是怎么把那段区间找出来。先把题目翻译成人话为了讲得顺后面换个说法把数组里每个数字看成一块饼干把移除看成拿走。规则一个字没改只是叫法变了。一排饼干每块上面写着重量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个累加和。收个尾这道题最关键的地方就是把问题反过来看。同一件事正面去算怎么拿走得先定左右各拿多少还要保证两边别重复拿最后再比一比谁拿得更少。反过来算怎么留下剩下的是一段连续区间要满足的条件只剩一条重量。这一换要防的坑少了一大半。前缀和配一本记事本是找连续区间和恰好等于某值的标准搭配。区间和、子数组和这一类的题很多都是它的变形。