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助力您的未來發展。