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

2026-04-26：使循环数组余额非负的最少移动次数。用go语言，给定一个环形排列的数组 balance，长度为 n，其中 balance[i] 表示第 i 个人当前的净余额（正数代表有剩余，负数代

news 2026/4/26 8:31:31

2026-04-26：使循环数组余额非负的最少移动次数。用go语言，给定一个环形排列的数组 balance，长度为 n，其中 balance[i] 表示第 i 个人当前的净余额（正数代表有剩余，负数代表欠债）。

在一次操作中，你可以选择某个人，把恰好 1 单位余额转给他的左邻居或右邻居（因为是环形，首尾相邻）。

目标：通过若干次这样的转移，使得所有位置的余额都变为非负（即每个人都不再欠债）。

要求：输出实现该目标的最小操作次数；如果从初始状态出发无法做到，则输出 -1。

已知条件：初始时数组中最多只有一个位置的余额为负。

1 <= n == balance.length <= 100000。

-1000000000 <= balance[i] <= 1000000000。

balance 中初始至多有一个负值。

输入：balance = [1,2,-5,2]。

输出：6。

解释：

一种最优的移动序列如下：

从 i = 1 移动 1 个单位到 i = 2，结果 balance = [1, 1, -4, 2]

从 i = 1 移动 1 个单位到 i = 2，结果 balance = [1, 0, -3, 2]

从 i = 3 移动 1 个单位到 i = 2，结果 balance = [1, 0, -2, 1]

从 i = 3 移动 1 个单位到 i = 2，结果 balance = [1, 0, -1, 0]

从 i = 0 移动 1 个单位到 i = 1，结果 balance = [0, 1, -1, 0]

从 i = 1 移动 1 个单位到 i = 2，结果 balance = [0, 0, 0, 0]

因此，所需的最小移动次数是 6。

题目来自力扣3776。

代码执行过程详细拆解

第一步：遍历数组，统计核心信息

计算数组所有元素的总和：1+2+(-5)+2 = 0
遍历过程中记录唯一的负数位置：只有索引2的值是-5，因此negIdx=2
基础校验：
- 总和=0 ≥ 0，满足可以完成的条件；
- 存在负数，需要计算移动次数。

第二步：确定核心需求

负数位置是索引2，余额为-5，需要补充5单位余额才能变成0（非负），记need=5（需要的总余额数）。
初始化总操作次数ans=0。

第三步：按距离分层收集余额（环形就近原则，最小步数）

因为是环形数组，我们从离负数位置最近的地方开始收集余额（距离越近，移动步数越少，符合最小操作次数要求），距离从1开始依次递增：

距离 dis=1（离索引2最近的左右邻居）

找环形数组中，距离negIdx=2为1的两个位置：
- 左邻居：(2-1+4)%4 = 1
- 右邻居：(2+1)%4 = 3
这两个位置的余额：索引1=2，索引3=2，总和s=2+2=4
计算：
- 当前需要5单位，这两个位置能提供4单位，全部用完
- 操作次数 += 4 × 1（4个单位，每个移动1步）→ ans=4
- 剩余需要的余额：need=5-4=1

距离 dis=2（下一层更远的位置）

找环形数组中，距离negIdx=2为2的两个位置：
- 左邻居：(2-2+4)%4 = 0
- 右邻居：(2+2)%4 = 0（环形数组，距离2时左右是同一个位置）
这个位置的余额：索引0=1，总和s=1
计算：
- 剩余只需要1单位，这个位置恰好能提供1单位
- 操作次数 += 1 × 2（1个单位，每个移动2步）→ ans=4+2=6
- need=0，需求满足，结束计算

第四步：返回结果

总操作次数为6，与题目示例输出一致。

时间复杂度与额外空间复杂度分析

1. 时间复杂度

第一步遍历数组：执行了n次操作（n是数组长度）；
第三步按距离收集余额：因为最多只有1个负数，且我们是就近收集，循环次数远小于n，可以视为常数次；
整体总操作次数与数组长度n成正比 →时间复杂度为 O(n)。

2. 额外空间复杂度

代码中只定义了total、negIdx、need、ans、dis、s等常数个变量；
没有创建任何与数组长度n相关的额外数组、集合等数据结构；
额外空间复杂度为 O(1)（常数级空间）。

总结

执行核心流程：统计总和→定位唯一负数→校验合法性→就近分层收集余额→累加步数→返回结果；
时间复杂度：O(n)（线性复杂度，适合题目n≤100000的大数据量）；
额外空间复杂度：O(1)（仅使用固定变量，无额外内存开销）。

Go完整代码如下：

packagemainimport("fmt")funcminMoves(balance[]int)int64{total:=0negIdx:=-1fori,x:=rangebalance{total+=xifx<0{negIdx=i}}iftotal<0{// 总和必须非负return-1}ifnegIdx<0{// 没有负数，无需操作return0}n:=len(balance)need:=-balance[negIdx]ans:=0fordis:=1;;dis++{// 把与 negIdx 相距 dis 的数移到 negIdxs:=balance[(negIdx-dis+n)%n]+balance[(negIdx+dis)%n]ifs>=need{ans+=need*dis// need 个 1 移动 dis 次returnint64(ans)}ans+=s*dis// s 个 1 移动 dis 次need-=s}}funcmain(){balance:=[]int{1,2,-5,2}result:=minMoves(balance)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdefminMoves(balance:List[int])->int:total=0neg_idx=-1fori,xinenumerate(balance):total+=xifx<0:neg_idx=iiftotal<0:# 总和必须非负return-1ifneg_idx<0:# 没有负数，无需操作return0n=len(balance)need=-balance[neg_idx]ans=0dis=1whileTrue:# 把与 neg_idx 相距 dis 的数移到 neg_idxleft=balance[(neg_idx-dis)%n]right=balance[(neg_idx+dis)%n]s=left+rightifs>=need:ans+=need*dis# need 个 1 移动 dis 次returnans ans+=s*dis# s 个 1 移动 dis 次need-=s dis+=1if__name__=="__main__":balance=[1,2,-5,2]result=minMoves(balance)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<cmath>usingnamespacestd;longlongminMoves(vector<int>&balance){inttotal=0;intnegIdx=-1;for(inti=0;i<balance.size();i++){total+=balance[i];if(balance[i]<0){negIdx=i;}}if(total<0){// 总和必须非负return-1;}if(negIdx<0){// 没有负数，无需操作return0;}intn=balance.size();intneed=-balance[negIdx];longlongans=0;for(intdis=1;;dis++){// 把与 negIdx 相距 dis 的数移到 negIdxintleft=balance[(negIdx-dis+n)%n];intright=balance[(negIdx+dis)%n];ints=left+right;if(s>=need){ans+=static_cast<longlong>(need)*dis;// need 个 1 移动 dis 次returnans;}ans+=static_cast<longlong>(s)*dis;// s 个 1 移动 dis 次need-=s;}}intmain(){vector<int>balance={1,2,-5,2};longlongresult=minMoves(balance);cout<<result<<endl;return0;}