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

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. 1. 计算数组所有元素的总和：1+2+(-5)+2 = 0

2. 2. 遍历过程中记录唯一的负数位置：只有索引2的值是-5，因此negIdx=2

3. 3. 基础校验：

• • 总和=0 ≥ 0，满足可以完成的条件；

• • 存在负数，需要计算移动次数。

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

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

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

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

1. 1. 找环形数组中，距离negIdx=2为1的两个位置：

• • 左邻居：(2-1+4)%4 = 1

• • 右邻居：(2+1)%4 = 3

2. 这两个位置的余额：索引1=2，索引3=2，总和s=2+2=4

3. 计算：

• • 当前需要5单位，这两个位置能提供4单位，全部用完

• • 操作次数 += 4 × 1（4个单位，每个移动1步）→ ans=4

• • 剩余需要的余额：need=5-4=1

1. 1. 找环形数组中，距离negIdx=2为2的两个位置：

• • 左邻居：(2-2+4)%4 = 0

• • 右邻居：(2+2)%4 = 0（环形数组，距离2时左右是同一个位置）

2. 这个位置的余额：索引0=1，总和s=1

3. 计算：

• • 剩余只需要1单位，这个位置恰好能提供1单位

• • 操作次数 += 1 × 2（1个单位，每个移动2步）→ ans=4+2=6

• • need=0，需求满足，结束计算

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

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

• • 第一步遍历数组：执行了n次操作（n是数组长度）；

• • 第三步按距离收集余额：因为最多只有1个负数，且我们是就近收集，循环次数远小于n，可以视为常数次；

• • 整体总操作次数与数组长度n成正比 →时间复杂度为 O(n)。

• • 代码中只定义了total、negIdx、need、ans、dis、s等常数个变量；

• • 没有创建任何与数组长度n相关的额外数组、集合等数据结构；

• •额外空间复杂度为 O(1)（常数级空间）。

1. 1. 执行核心流程：统计总和→定位唯一负数→校验合法性→就近分层收集余额→累加步数→返回结果；

2. 2. 时间复杂度：O(n)（线性复杂度，适合题目n≤100000的大数据量）；

3. 3. 额外空间复杂度：O(1)（仅使用固定变量，无额外内存开销）。

package main

 import (
    "fmt"
)

 func minMoves(balance []int)int64 {
    total := 0
    negIdx := -1
    for i, x := range balance {
        total += x
        if x < 0 {
            negIdx = i
        }
    }

     if total < 0 { // 总和必须非负
        return-1
    }
    if negIdx < 0 { // 没有负数，无需操作
        return0
    }

     n := len(balance)
    need := -balance[negIdx]
    ans := 0
    for dis := 1; ; dis++ { // 把与 negIdx 相距 dis 的数移到 negIdx
        s := balance[(negIdx-dis+n)%n] + balance[(negIdx+dis)%n]
        if s >= need {
            ans += need * dis // need 个 1 移动 dis 次
            returnint64(ans)
        }
        ans += s * dis // s 个 1 移动 dis 次
        need -= s
    }
}

 func main() {
    balance := []int{1, 2, -5, 2}
    result := minMoves(balance)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def minMoves(balance: List[int]) -> int:
    total = 0
    neg_idx = -1
    for i, x in enumerate(balance):
        total += x
        if x < 0:
            neg_idx = i
    if total < 0:  # 总和必须非负
        return-1
    if neg_idx < 0:  # 没有负数，无需操作
        return0
    n = len(balance)
    need = -balance[neg_idx]
    ans = 0
    dis = 1
    while True:  # 把与 neg_idx 相距 dis 的数移到 neg_idx
        left = balance[(neg_idx - dis) % n]
        right = balance[(neg_idx + dis) % n]
        s = left + right
        if s >= need:
            ans += need * dis  # need 个 1 移动 dis 次
            return ans
        ans += s * dis  # s 个 1 移动 dis 次
        need -= s
        dis += 1

 if __name__ == "__main__":
    balance = [1, 2, -5, 2]
    result = minMoves(balance)
    print(result)

C++完整代码如下：

  

  

  


 using namespace std;

 long long minMoves(vector& balance) {
    int total = 0;
    int negIdx = -1;

     for (int i = 0; i < balance.size(); i++) {
        total += balance[i];
        if (balance[i] < 0) {
            negIdx = i;
        }
    }

     if (total < 0) { // 总和必须非负
        return-1;
    }
    if (negIdx < 0) { // 没有负数，无需操作
        return0;
    }

     int n = balance.size();
    int need = -balance[negIdx];
    long long ans = 0;

     for (int dis = 1; ; dis++) { // 把与 negIdx 相距 dis 的数移到 negIdx
        int left = balance[(negIdx - dis + n) % n];
        int right = balance[(negIdx + dis) % n];
        int s = left + right;

         if (s >= need) {
            ans += static_cast 
 
 (need) * dis;  
 // need 个 1 移动 dis 次
            return ans;
        }
        ans += static_cast 
 
 (s) * dis;  
 // s 个 1 移动 dis 次
        need -= s;
    }
}

 int main() {
    vector balance = {1, 2, -5, 2};
    long long result = minMoves(balance);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。