华为OD 机试 2025-阿里巴巴找黄金宝箱（1）

📝 题目描述：寻找“黄金宝箱”

一贫如洗的樵夫阿里巴巴在前往山中砍柴的路上，意外发现了强盗集团的藏宝地。藏宝地中整齐摆放着编号从 0 到 N-1 的若干个宝箱，每个宝箱上贴有一个整数（可能为负数），其中可能存在一个黄金宝箱。

黄金宝箱的定义如下：

它左侧所有宝箱上数字之和，等于右侧所有宝箱上数字之和。

你的任务是：找出编号最小的那个黄金宝箱。如果不存在，请输出 -1。

📥 输入描述

输入为一行字符串，表示所有宝箱上的贴纸数字，使用英文逗号,分隔。

• 宝箱个数：1 ≤ N ≤ 1000
• 每个数字范围：-1000 ≤ 数字 ≤ 1000

示例：

2,5,-1,8,6

📤 输出描述

输出满足条件的第一个黄金宝箱编号（从0开始计数），如果不存在，则输出 -1。

📌 示例

示例 1

输入：

2,5,-1,8,6

输出：

3

解释：
下标 3 之前的数和为 2+5+(-1)=6，之后的数为 6，满足条件。

示例 2

输入：

8,9

输出：

-1

解释：
任意位置都不满足左右和相等条件。

示例 3

输入：

11

输出：

0

解释：
仅一个元素，左边和右边都为 0，满足条件。

🧠 解题思路解析

目标：找第一个索引 i，满足：

sum(0 ~ i-1) == sum(i+1 ~ N-1)

算法步骤：

1. 使用一个变量记录 left_sum = 0，表示左侧和；

2. 预先求出 total_sum 表示所有元素之和；

3. 遍历每个索引 i，当前值为 nums[i]；

   • 当前的右侧和：right_sum = total_sum - left_sum - nums[i]
   • 如果 left_sum == right_sum，则返回该索引；
   • 否则更新 left_sum += nums[i]；

4. 遍历结束仍未找到则返回 -1。

时间复杂度：

• 时间复杂度：O(N)，仅一次遍历；
• 空间复杂度：O(1)，使用常量空间。

✅ Python 实现

def find_gold_box(nums):
    left_sum = 0
    total_sum = sum(nums)
    for i, val in enumerate(nums):
        right_sum = total_sum - left_sum - val
        if left_sum == right_sum:
            return i
        left_sum += val
    return -1

if __name__ == "__main__":
    nums = list(map(int, input().strip().split(',')))
    print(find_gold_box(nums))

✅ Java 实现

import java.util.*;

public class Main {
    public static int findGoldBox(int[] nums) {
        int leftSum = 0, total = 0;
        for (int num : nums) total += num;
        for (int i = 0; i < nums.length; i++) {
            int rightSum = total - leftSum - nums[i];
            if (leftSum == rightSum) return i;
            leftSum += nums[i];
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] parts = sc.nextLine().split(",");
        int[] nums = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            nums[i] = Integer.parseInt(parts[i].trim());
        }
        System.out.println(findGoldBox(nums));
        sc.close();
    }
}

✅ JavaScript 实现（Node.js 环境）

function findGoldBox(nums) {
  let total = nums.reduce((a, b) => a + b, 0);
  let leftSum = 0;
  for (let i = 0; i < nums.length; i++) {
    const rightSum = total - leftSum - nums[i];
    if (leftSum === rightSum) return i;
    leftSum += nums[i];
  }
  return -1;
}

// Node.js 输入处理
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', line => {
  const nums = line.split(',').map(Number);
  console.log(findGoldBox(nums));
  rl.close();
});

🏁 总结