20天拿下华为OD笔试之【模拟】2023B-阿里巴巴找黄金宝箱(1)【欧弟算法】全网注释最详细分类最全的华为OD真题题解

【模拟】2023B-阿里巴巴找黄金宝箱(1)

题目描述与示例

题目描述

一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从 0~N 的箱子，每个箱子上面贴有一个数字，箱子中可能有一个黄金宝箱。

黄金宝箱满足排在它之前的所有箱子数字和等于排在它之后的所有箱子数字和；

第一个箱子左边部分的数字和定义为 0；

最后一个宝箱右边部分的数字和定义为 0。

请帮阿里巴巴找到黄金宝箱，输出第一个满足条件的黄金宝箱编号，如果不存在黄金宝箱，请返回-1。

输入描述

箱子上贴的数字列表，使用逗号分隔，例如 1，-1，0。

宝箱的数量不小于 1 个，不超过 10000

宝箱上贴的数值范围不低于-1000，不超过 1000

输出描述

第一个黄金宝箱的编号

示例一

输入

2,5,-1,8,6
1

输出

3
1

说明

下标 3 之前的数字和为：2 + 5 + -1 = 6

下标 3 之后的数字和为：6 = 6

示例二

输入

8,9
1

输出

-1
1

说明

不存在符合要求的位置

示例三

输入

11
1

输出

0
1

说明

下标 0 之前的数字和为：0

下标 0 之后的数字和为：0

解题思路

本题较为简单，直接依据题意模拟即可。

考虑0号箱子，初始化两个变量 left_sum = 0 和 right_sum = sum(nums[1:]) 分别表示左、右两边所有箱子和。当考虑第i号箱子时

• 右边箱子和 right_sum 不再考虑第i号箱子，应该减掉 nums[i]
• 左边箱子和left_sum要考虑第i-1号箱子，应该加上nums[i-1]
• 若做完加减后，两者相等，则i为找到的第一个黄金箱子

上述逻辑过程整理为代码即为

ans = -1
for i, num in enumerate(nums[1:], 1):
    right_sum -= num
    left_sum += nums[i-1]
    if right_sum == left_sum:
        ans = i
        break
1
2
3
4
5
6
7

实际上，本题的算法过程也可以看作是一个长度为1的固定滑窗。如果用滑窗三问三答来思考问题也未尝不可。

代码

# 题目：2023B-阿里巴巴找黄金宝箱
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：模拟
# 代码看不懂的地方，请直接在群上提问



nums = list(map(int, input().split(",")))

# 初始化左边和为0
left_sum = 0
# 初始化右边和为除了0号宝箱之外，其他剩余所有宝箱的和
right_sum = sum(nums[1:])

# 如果right_sum为0，则0号宝箱为黄金宝箱，直接输出
if right_sum == 0:
    print(0)
else:
    # 初始化答案变量ans = -1
    ans = -1
    # 遍历剩余所有宝箱的索引i和值num
    for i, num in enumerate(nums[1:], 1):
        # 对于i号宝箱而言，
        # 其右边所有宝箱和为 right_sum - num
        # 其左边所有的宝箱和为 left_sum + nums[i-1]
        right_sum -= num
        left_sum += nums[i-1]
        # 如果i号宝箱左右两边宝箱和相等，则i为答案
        # 修改ans为i，并且退出循环
        if right_sum == left_sum:
            ans = i
            break

    # 输出答案变量
    # 如果在上述循环中从未出现过right_sum == left_sum
    # 则ans维持-1，表示没有黄金宝箱
    print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时空复杂度

时间复杂度：O(N)。仅需一次遍历数组。

空间复杂度：O(1)。仅需若干常数变量。

---

华为OD算法冲刺训练

• 华为OD算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 30+天陪伴式学习，20+直播课时，300+动画图解视频，200+LeetCode经典题，100+华为OD真题，还有简历修改与模拟面试将为你解锁

• 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多