首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【前缀和】算法思想,附两道道手撕题

【前缀和】算法思想,附两道道手撕题

作者头像
鳄鱼儿
发布于 2024-12-29 01:26:10
发布于 2024-12-29 01:26:10
26900
代码可运行
举报
运行总次数:0
代码可运行

在算法设计和优化中,前缀和算法是一种简单而强大的技术,它通过预处理数组数据来加速对数组子区间和的查询。

这种算法思想特别适用于需要频繁计算数组中连续子区间和的场景,如数据流问题、区间查询问题等。本文将详细介绍前缀和算法的思想、实现步骤以及其应用场景。

前缀和算法思想概述

前缀和算法的核心思想是预先计算并存储数组中每个位置之前所有元素的累积和,这样在需要计算任意子区间和时,可以直接通过查找前缀和数组中的特定元素来快速得出结果。

算法实现步骤

1. 计算前缀和数组

前缀和数组的构建是算法的第一步。给定一个数组 A,长度为 n,我们创建一个新的数组 sum,其中 sum[i] 表示数组 A 中从第一个元素到第 i 个元素的累积和。具体计算方法如下:

image.png
image.png

这个步骤的时间复杂度为 (O(n)),其中 n 是数组 A 的长度。

2. 利用前缀和数组计算子区间和

一旦构建了前缀和数组,计算任意子区间 [i, j] 的和变得非常简单。子区间和可以通过以下公式快速计算:

image.png
image.png

这里需要注意的是,由于 sum[0] 存储的是数组的第一个元素,所以当 i = 0 时,公式变为 sum[j],因为 sum[0]sum[i-1] 相等。

前缀和算法因其高效性,在多种算法问题中都有应用。以下是一些常见的应用场景:

  • 区间查询:快速响应对数组中任意区间元素和的查询。
  • 动态规划:在某些动态规划问题中,前缀和可以用来优化状态转移。
  • 数据流问题:处理动态数据流,快速计算窗口内元素的和。
  • 在线算法:在线算法中,前缀和可以用来处理实时数据流的问题。

动态数组的考虑

正如前文所述,前缀和算法在处理静态数组时非常有效。

然而,如果数组是动态变化的,即元素的值或位置会发生变化,那么可能需要定期重新计算前缀和数组,这会增加额外的计算开销。

在这种情况下,需要根据具体问题的特点来权衡使用前缀和算法的利弊。

算法题

分割数组的最大差值

描述

给定一个由若干整数组成的数组nums ,可以在数组内的任意位置进行分割,将该数组分割成两个非空子数组(即左数组和右数组),分别对子数组求和得到两个值,计算这两个值的差值,请输出所有分割方案中,差值最大的值。

输入描述

第一行输入数组中元素个数n,1 < n ≤ 100000 第二行输入数字序列,以空格进行分隔,数字取值为4字节整数

输出描述

输出差值的最大取值

题解

具体的步骤如下:

  1. 初始化变量
    • leftSum:初始化为0,表示左数组的和。
    • rightSum:初始化为数组总和,表示右数组的和。
    • maxDiff:初始化为0,用于存储最大的绝对差值。
  2. 遍历数组
    • 从数组的第一个元素开始,遍历到倒数第二个元素。
  3. 更新和计算
    • 在每次循环中:
      • 将当前元素累加到leftSum
      • rightSum中减去当前元素。
      • 计算当前的绝对差值:Math.abs(leftSum - rightSum)
      • 如果当前的绝对差值大于maxDiff,则更新maxDiff为这个新的差值。
  4. 输出结果
    • 遍历结束后,maxDiff将包含最大的绝对差值,输出这个值。
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import sys

# 读取输入的数组长度
length = int(sys.stdin.readline())

# 读取数字序列,并将其转换为整数列表
numbers = list(map(int, sys.stdin.readline().split()))

# 初始化前缀和数组,用于快速计算任意区间的和
prefixSum = [0] * length
prefixSum[0] = numbers[0]
for i in range(1, length):
    prefixSum[i] = prefixSum[i - 1] + numbers[i]

# 初始化最大差值变量
maxDifference = 0

# 遍历数组,计算每个分割点的左右数组和的差值
for i in range(length - 1):
    # 计算当前分割点左边数组的和
    leftSum = prefixSum[i]
    # 计算当前分割点右边数组的和
    rightSum = prefixSum[length - 1] - prefixSum[i]
    # 计算左右数组和的绝对差值
    difference = abs(leftSum - rightSum)
    # 更新最大差值
    maxDifference = max(maxDifference, difference)

# 输出最大差值
print(maxDifference)

查找接口成功率最优时间段

描述

服务之间交换的接口成功率作为服务调用关键质量特性,某个时间段内的接口失败率使用一个数组表示,

数组中每个元素都是单位时间内失败率数值,数组中的数值为0~100的整数,

给定一个数值(minAverageLost)表示某个时间段内平均失败率容忍值,即平均失败率小于等于minAverageLost,

找出数组中最长时间段,如果未找到则直接返回NULL。

输入描述

输入有两行内容,第一行为{minAverageLost},第二行为{数组},数组元素通过空格(” “)分隔,

minAverageLost及数组中元素取值范围为0~100的整数,数组元素的个数不会超过100个。

输出描述

找出平均值小于等于minAverageLost的最长时间段,输出数组下标对,格式{beginIndex}-{endIndx}(下标从0开始),

如果同时存在多个最长时间段,则输出多个下标对且下标对之间使用空格(” “)拼接,多个下标对按下标从小到大排序。

题解

解题思路如下:

  1. 数据读取:首先,我们需要从输入中获取两个关键参数:允许的平均失败率阈值以及记录失败率的数据数组。
  2. 构建累积和数组:为了高效计算任意子区间的失败率总和,我们构建一个累积和数组。该数组的每个元素代表从数组起点到当前位置的失败率累加值。
  3. 遍历子区间:接着,我们遍历所有可能的子区间,即所有可能的起始和结束索引组合。对于每个子区间,我们利用累积和数组快速确定该区间的失败率总和,并据此计算平均失败率。
  4. 条件检查:对于每个子区间,我们验证其平均失败率是否不超过允许的阈值。如果满足条件,即记录该子区间。
  5. 寻找最长子区间:在记录满足条件的子区间时,我们同时追踪最长的子区间长度。一旦发现更长的子区间,即更新最长长度,并重置结果列表,将新子区间加入。若发现等长的子区间,则直接添加到结果列表中。
  6. 结果输出:最后,我们检查结果列表。若为空,则表示没有找到任何符合条件的子区间,输出"NULL"。否则,输出所有符合条件的子区间,若有多个,则按起始索引的升序排列。

通过这种方法,我们利用累积和数组高效地计算子区间失败率总和,并借助结果列表追踪所有满足条件的子区间,从而在单次遍历中找到所有符合条件的子区间,并快速确定最长的子区间。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# 读取输入的整数n,代表允许的平均失败率阈值
n = int(input())

# 读取输入的数字列表,并将其转换为整数列表
nums = list(map(int, input().split()))

# 获取列表的长度
m = len(nums)

# 初始化前缀和数组,长度为m+1,多一个0用于方便计算
preSum = [0] * (m + 1)

# 用于存储每个长度的子区间及其对应的索引范围
ans = {}

# 计算前缀和
for i in range(m):
    preSum[i + 1] = preSum[i] + nums[i]

# 使用滑动窗口优化算法遍历所有子区间
for i in range(m):
    for j in range(i, m):
        # 计算子区间的和
        subSum = preSum[j + 1] - preSum[i]  
        # 计算子区间的长度
        cnt = j - i + 1
        # 检查子区间的平均值是否小于等于允许的平均失败率阈值
        if subSum / cnt <= n:
            # 如果该长度的子区间已存在于ans字典中,则追加索引范围
            if cnt in ans:
                ans[cnt].append(f'{i}-{j}')
            # 否则,创建一个新的列表存储该长度的子区间索引范围
            else:
                ans[cnt] = [f'{i}-{j}']

# 找到最长的子区间长度
maxL = max(ans.keys())

# 输出最长子区间的所有索引范围,以空格分隔
print(' '.join(ans[maxL]))
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-12-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
一篇带你速通前缀和算法(C/C++)
前缀和是一种常见的算法计算技巧,通常用于处理数组或序列的连续子区间求和问题。它可以帮助我们在 O(1) 的时间内计算出指定子区间的和,而不需要每次都遍历整个子区间。前缀和一般用于预处理当中,具有高效率的特点。
摆烂小白敲代码
2024/09/23
2280
一篇带你速通前缀和算法(C/C++)
【数据结构与算法】常用算法 前缀和
对于一个给定的数组或序列,我们定义前缀和数组prefixSum,其中prefixSum[i]表示原数组中前i个元素的和。即prefixSum[i] = nums[0] + nums[1] + ... + nums[i-1]。特别地,prefixSum[0] = 0。
苏泽
2024/03/01
3160
前缀和数组(算法)
前缀和(Prefix Sum)是指数组中某个位置之前的所有元素的和。对于数组 arr,其前缀和数组 prefixSum 定义为:
猫咪-9527
2025/01/13
1610
前缀和数组(算法)
【优选算法篇】滑动窗口的艺术:如何动态调整子区间解决复杂问题(中篇)
接上篇:【优选算法篇】一文读懂滑动窗口:动态调整范围的算法利器(上篇)-CSDN博客
熬夜学编程的小王
2024/12/24
2630
【优选算法篇】滑动窗口的艺术:如何动态调整子区间解决复杂问题(中篇)
备战蓝桥杯————前缀和数组1
定义:前缀和数组(Prefix Sum Array)是一个数组,它存储了原数组(或序列)的连续子数组之和。对于一个给定的数组 nums,其前缀和数组 cumulativeSum 的第 i 个元素 cumulativeSum[i] 表示 nums 从第一个元素到第 i 个元素的累加和。
小小程序员
2024/02/29
1650
【贪心】算法思想,附两道道手撕题
贪心思想是一种解决问题的方法,它通过在每一步选择中都采取最好或者最优的选择,以期望最终结果也是最好或者最优的。
鳄鱼儿
2024/12/29
1960
LeetCode294,手速场周赛,12分钟切3题卡到比赛结束……
今天我们照惯例来看下LeetCode周赛,这一场的比赛由普渡机器人赞助,前300名的同学可以获得内推机会。
TechFlow-承志
2022/09/21
3010
LeetCode294,手速场周赛,12分钟切3题卡到比赛结束……
Leetcode【523、525、560、974】
这道题是给一个非负整数数组和整数 k,判断数组是否含有连续子数组,其大小至少为 2,总和为 k 的倍数,即总和为 n*k,其中 n 也是一个整数。
echobingo
2019/07/11
6870
拼多多算法题,是清华考研真题!
不仅是拼多多,该题还在诸如 神州信息 和 滴滴出行 这样的互联网大厂笔试中出现过:
宫水三叶的刷题日记
2023/12/13
4240
拼多多算法题,是清华考研真题!
【数据结构和算法】寻找数组的中心下标
这是力扣的 724 题,难度为简单,解题方案有很多种,本文讲解我认为最奇妙的一种。
绿毛龟
2024/01/19
2040
【数据结构和算法】寻找数组的中心下标
【算法一周目】从时光的边缘看世界:前缀和揭示的算法真谛
给定一个长度为 n 的整数数组 arr 和 q 个查询,每个查询由两个整数 l 和 r 组成,表示区间 [l, r]。请计算出每个区间内所有元素的和。
HZzzzzLu
2024/12/31
1120
【算法一周目】从时光的边缘看世界:前缀和揭示的算法真谛
【优选算法】Prefix-Kage:前缀和的算法影(上)
🚩什么是前缀和算法? 前缀和算法是一种用于高效计算数组区间和的算法。对于一个给定的数组 nums,我们可以预先计算出它的前缀和数组 prefixSum ,其中 prefixSum[i] 表示 nums[0] 到 nums[i] 的元素之和
DARLING Zero two
2024/12/24
810
【优选算法】Prefix-Kage:前缀和的算法影(上)
Leetcode | 第B节:数组综合题(2)
抱歉这一节相对隔得时间长了一些再发出来,因为这几天基本上主要时间都在关注东京奥运会的比赛现场。在发表这篇文章的时候,也恰好知道名将苏炳添以9‘83’‘的时间晋级决赛,我认为他可以以这个成绩再拿一次金牌,希望我的预言成真2333
学弱猹
2021/08/06
4400
【刷题】前缀和入门
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆
叫我龙翔
2024/04/25
1010
【刷题】前缀和入门
深度解析算法之前缀和
这个题的话就是下面的样子,我们第一行输入 3 2的意思即是这个数组是3个元素大小的数组,2是接下来我们是需要输入两行数据下标的 然后第二行我们输入的n个整数表示的就是我们数组中的元素 然后后面的2行就是我们想计算数组中从哪里到哪里的和 这里的话我们是第一个数到第二个数的和,那么我们这里的就是3了
Undoom
2025/04/21
830
深度解析算法之前缀和
【优选算法篇】解密前缀和:让数组求和变得如此高效(上篇)
前缀和算法是解决一类常见数组问题的高效方法。它的核心价值在于将多次重复计算的部分进行优化,使得对数组的多次区间求和操作能在常数时间内完成。它不仅可以大幅减少时间复杂度,还能够应用于各种问题,如数组求和、子数组的最大/最小和等。
熬夜学编程的小王
2024/12/24
2210
【优选算法篇】解密前缀和:让数组求和变得如此高效(上篇)
前缀和算法详解
和一维的前缀和数组类似,这里需要先预处理出来一个前缀和矩阵 dp[][],dp[i][j] 就表示从(1,1)到(i,j)这个矩阵中的所有元素的和
2的n次方
2024/10/15
1280
前缀和算法详解
leetcode 1208. 尽可能使字符串相等-----滑动窗口篇五,前缀和篇一,二分篇一
枚举 s 的所有子串,判断当前和 t 中的子串的「汉明距离」总和是否不大于 maxCost ,更新最大长度即可。
大忽悠爱学习
2021/11/15
7240
【西法带你学算法】一次搞定前缀和
我花了几天时间,从力扣中精选了五道相同思想的题目,来帮助大家解套,如果觉得文章对你有用,记得点赞分享,让我看到你的认可,有动力继续做下去。
lucifer210
2020/10/26
8690
【西法带你学算法】一次搞定前缀和
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
prefix表示前缀和,前缀和由一个用户输入的数组生成。对于一个数组a[](下标从1开始),我们定义一个前缀和数组prefix[],满足:
走在努力路上的自己
2024/03/04
3120
前缀和算法题(区间次方和、小蓝平衡和、大石头的搬运工、最大数组和)
推荐阅读
相关推荐
一篇带你速通前缀和算法(C/C++)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验