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

福大大架构师每日一题

发布于 2026-04-28 19:44:28

130

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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+2+(-5)+2 = 0
2. 遍历过程中记录唯一的负数位置：只有索引2的值是-5，因此negIdx=2
3. 基础校验：
- • 总和=0 ≥ 0，满足可以完成的条件；
- • 存在负数，需要计算移动次数。

第二步：确定核心需求

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

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

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

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

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

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

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)。

2. 额外空间复杂度

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

总结

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

Go完整代码如下：

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++完整代码如下：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

long long minMoves(vector<int>& 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<long long>(need) * dis; // need 个 1 移动 dis 次
            return ans;
        }
        ans += static_cast<long long>(s) * dis; // s 个 1 移动 dis 次
        need -= s;
    }
}

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