2

Prefix Sum | 一直进步 做喜欢的

 1 year ago
source link: https://xfliu1998.github.io/2023/03/22/Prefix-Sum/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一直进步 做喜欢的

Prefix Sum

Created2023-03-22|Updated2023-03-22|Data Structures and Algorithms
Word count:678|Reading time:2min|Post View:1|Comments:
  • 简介：前缀和算法是一种常见的数组处理算法，通过预处理出数组的前缀和（Prefix Sum），可以在O(1)时间内快速求出任意区间的和。
  • 计算方式：对于一个长度为n的数组a，其前缀和数组prefix_sum的第i个元素表示a数组中前i-1个元素的和，计算公式为prefix_sum[i+1] = prefix_sum[i] + a[i]。初始化prefix_sum=[0]*(len(a)+1)。
  • 使用前缀和算法求解区间和：假设要求区间[l,r]的和，可以通过计算prefix_sum[r+1]-prefix_sum[l]来得到区间和。这是因为prefix_sum[r+1]表示a数组前r个元素的和，prefix_sum[l]`表示a数组前l-1个元素的和，两者相减即可得到区间[l,r]的和。
  • 应用场景：处理数组序列问题，如求解子数组的和、平均数、中位数等。也可以用于处理二维矩阵中的子矩阵问题。
  • 时间复杂度：预处理时间复杂度为O(n)，求解区间和的时间复杂度为O(1)，因此总的时间复杂度为O(n)。
# 判断数组内是否有等于k的连续子数组，或者有几个
def prefix_search(self, k: int, nums: List[int]) :
    # 计算前缀和数组，有时可以边遍历边计算，不用单独先计算前缀和
    pre_sum = [0] * (len(nums) + 1)
    for i in range(len(nums)):
        pre_sum[i+1] = pre_sum[i] + nums[i]
    for i in range(len(nums) + 1):
        # 记录子前缀和信息
        dict[pre_sum[i]] += 1
        # 边遍历边记录前缀和
        # pre_sum += nums[i]
        # 转换问题pre_sum[i] - pre_sum[j] = k
        target = pre_sum[i] - k
        # 判断target是否满足什么条件，返回结果（通常通过字典查询）
        if target in dict:
            ans...
前缀和
题目 技巧 难度
✅209. 长度最小的子数组 前缀和+二分bisect 🌟🌟
✅238. 除自身以外数组的乘积 分别计算前后缀乘积 🌟🌟
✅303. 区域和检索 - 数组不可变 一维前缀和 🌟
✅304. 二维区域和检索 - 矩阵不可变 二维前缀和 🌟🌟
❌363. 矩形区域不超过 K 的最大数值和 二分+有序集合 🌟🌟🌟
✅523. 连续的子数组和 sum[i]-sum[j]=n*k等效于sum[i]和sum[j]对k的余数相等，用哈希记录 🌟🌟
✅525. 连续数组 转换问题：求最长的连续子数组，其元素和为0 🌟🌟
✅560. 和为 K 的子数组 sum[i]-sum[j]=k转化成sum[j]=sum[i]-k，用哈希记录 🌟🌟
✅724. 寻找数组的中心下标 & 1991 🌟
✅930. 和相同的二元子数组 同974 🌟🌟
✅974. 和可被 K 整除的子数组 同523，需要初始化{0:1}来记录前缀总和的情况 🌟🌟

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK