python前缀和详解+蓝桥杯练习题--巧克力
1.前缀和的基本概念
前缀和是一种重要的预处理技术，常用于快速计算数组中某个区间内元素的总和。对于一个给定的数组 arr，其前缀和数组 prefix_sum 的每个元素 prefix_sum[i] 表示原数组 arr 中从索引 0 到索引 i 的所有元素的总和。
设原数组为 arr = [a₀, a₁, a₂, ..., aₙ₋₁]，那么前缀和数组 prefix_sum 满足：
prefix_sum[0] = arr[0]
prefix_sum[1] = arr[0] + arr[1]
prefix_sum[2] = arr[0] + arr[1] + arr[2]
...
prefix_sum[i] = arr[0] + arr[1] + ... + arr[i]2.前缀和的用法
前缀和的主要用途是高效地计算数组中任意区间 [left, right]（其中 left 和 right 分别是区间的起始和结束索引）内元素的总和。计算区间和的公式为：
当 left > 0 时，区间 [left, right] 的和 sum = prefix_sum[right] - prefix_sum[left - 1]
当 left == 0 时，区间 [left, right] 的和 sum = prefix_sum[right]通过使用前缀和，计算区间和的时间复杂度从直接遍历区间的O(n)降低到了O(1)，其中 n 是区间的长度。
3.举例解释
假设有一个数组 arr = [1, 3, 5, 7, 9]，来计算它的前缀和数组，并使用前缀和数组计算区间 [1, 3] 内元素的总和（即3+5+7）。
3.1 计算前缀和数组：
prefix_sum[0] = arr[0] = 1
prefix_sum[1] = arr[0] + arr[1] = 1 + 3 = 4
prefix_sum[2] = arr[0] + arr[1] + arr[2] = 1 + 3 + 5 = 9
prefix_sum[3] = arr[0] + arr[1] + arr[2] + arr[3] = 1 + 3 + 5 + 7 = 16
prefix_sum[4] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] = 1 + 3 + 5 + 7 + 9 = 25
# 所以前缀和数组 prefix_sum = [1, 4, 9, 16, 25]。将上述代码转化为：
prefix_sum[0] = arr[0] = 1
prefix_sum[1] = prefix_sum[0] + arr[1] = 1 + 3 = 4
prefix_sum[2] = prefix_sum[1] + arr[2] = 4 + 5 = 9
prefix_sum[3] = prefix_sum[2] + arr[3] = 9 + 7 = 16
prefix_sum[4] = prefix_sum[3] + arr[4] = 16 + 9 = 25
# 可以看出prefix_sum[i] = prefix_sum[i-1] + arr[i]前缀和数组 prefix_sum = [1, 4, 9, 16, 25]
3.2 计算区间内元素的总和：
# 根据公式，区间 [1, 3] 的和
sum = prefix_sum[3] - prefix_sum[1 - 1] = prefix_sum[3] - prefix_sum[0] = 16 - 1 = 15。
# 根据公式，区间 [2, 3] 的和
sum = prefix_sum[3] - prefix_sum[2 - 1] = prefix_sum[3] - prefix_sum[1] = 16 - 4 = 12。3.3 完整代码
def prefix_sum(arr):
n = len(arr)
# 初始化前缀和数组
prefix_sum = [0] * n
# 计算前缀和数组的第一个元素
prefix_sum[0] = arr[0]
# 遍历数组，计算前缀和数组的其余元素
for i in range(1, n):
prefix_sum[i] = prefix_sum[i - 1] + arr[i]
return prefix_sum
def range_sum(prefix_sum, left, right):
if left == 0:
return prefix_sum[right]
else:
return prefix_sum[right] - prefix_sum[left - 1]
# 示例数组
arr = [1, 3, 5, 7, 9]
# 计算前缀和数组
prefix_sum = prefix_sum(arr)
# 计算区间 [1, 3] 内元素的总和
left, right = 1, 3
range_sum = range_sum(prefix_sum, left, right)
print("原数组:", arr)
print("前缀和数组:", prefix_sum)
print(f"区间 [{left}, {right}] 内元素的总和:", range_sum)4.蓝桥杯练习--巧克力
4.1 题目简述
从左右两端分别开始向中间相加，直到两个值相等，不符合条件输出0
4.2 方法一：前缀和
- 如果左列和与右列和相同，赋值给max，左右两边同时再加和一个
- 如果左边大，则右边再加一个
- 如果右边大，则左边再加一个
- 循环直到两边选的盒子数等于总数n
- 输出最大值
n=int(input())
box=list(map(int,input().split()))
#计算前缀和
prefix=[0]*(n+1)
for i in range(1,n+1):
prefix[i]=prefix[i-1]+box[i-1]
#得到一组已经计算出和的列表
#利用双指针遍历box列表，先初始化指针
left=1
right=n
max_cho=0
while left<right: #当左指针和右指针相等时，结束循环【指针相当于一种索引】
left_sum=prefix[left]
right_sum=prefix[n]-prefix[right-1]
if left_sum==right_sum:
max_cho=max(max_cho,left_sum) #更新最大值
left+=1 #这两句很重要，要不然会陷入死循环
right-=1 #意味着每一步都要加入更新循环体的语句
#以下是一组循环体
elif left_sum<right_sum:
left+=1
else:
right-=1
print(max_cho)
4.3 方法二：双指针
- 如果左列和与右列和相同，赋值给ans，继续判断
- 如果左边大，则右边再加一个
- 如果右边大，则左边再加一个
- 循环直到两个指针重合
n=int(input())
lis=list(map(int,input().split()))
left=0
right=len(lis)-1
sum_left=lis[left]
sum_right=lis[right]
ans=0
while left<right:
if sum_left==sum_right:
ans=sum_right
if sum_left<sum_right:
left+=1
sum_left+=lis[left]
else:
right-=1
sum_right+=lis[right]
print(ans)