刷题笔记合集🔗

问题描述

阿里巴巴发现了一个藏宝地，里面有编号从0到N的箱子，每个箱子上贴有一个数字。其中可能有一个黄金宝箱，满足：

1. 该箱子之前的所有箱子数字和等于该箱子之后的所有箱子数字和
2. 第一个箱子左边的数字和定义为0
3. 最后一个箱子右边的数字和定义为0

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

输入格式

输入一个数字字符串，数字之间用逗号分隔。

输出格式

输出第一个满足条件的黄金宝箱编号，不存在则输出-1。

样例输入1

2,5,-1,8,6

样例输出1

3

样例输入2

8,9

样例输出2

-1

样例解释

样例1中：

• 下标3之前的数字和：2 + 5 + (-1) = 6
• 下标3之后的数字和：6
• 左右和相等，因此下标3是黄金宝箱的位置

数据范围

• 数组长度：
• 数字范围：

题解

这道题可以用前缀和思想来解决：

1. 先计算整个数组的总和
2. 用两个变量记录左边和右边的和
3. 遍历每个位置，更新左右两边的和并比较

时间复杂度：，其中n是数组长度。

参考代码

def get_result(nums):
    # 计算右边的和（不包括第一个数）
    right_sum = sum(nums) - nums[0]
    left_sum = 0
    
    # 检查第一个位置
    if left_sum == right_sum:
        return 0
    
    # 遍历其他位置
    for i in range(1, len(nums)):
        left_sum += nums[i-1]
        right_sum -= nums[i]
        if left_sum == right_sum:
            return i
    
    return -1

# 输入处理
nums = list(map(int, input().split(',')))
print(get_result(nums))

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <numeric>
using namespace std;

int solve(vector<int>& nums) {
    // 计算右边的和（不包括第一个数）
    int right_sum = accumulate(nums.begin(), nums.end(),