当前位置: 首页> 科技> 数码 > 商标转让费用_每日英语新闻_外贸网站如何推广优化_家电企业网站推广方案

商标转让费用_每日英语新闻_外贸网站如何推广优化_家电企业网站推广方案

时间:2025/7/11 8:22:20来源:https://blog.csdn.net/weixin_37253733/article/details/146438007 浏览次数:0次
商标转让费用_每日英语新闻_外贸网站如何推广优化_家电企业网站推广方案

📖 摘要

前缀和(Prefix Sum)是算法竞赛和面试中的高频考点,能将区间和查询从O(n)优化到O(1),还能结合哈希表高效统计满足条件的子数组。本文将深入浅出讲解前缀和的核心思想、应用场景,并通过LeetCode经典题目带你彻底掌握这一算法技巧!


📚 目录

  1. 什么是前缀和?
  2. 前缀和的应用场景
  3. 一维前缀和经典例题
  4. 二维前缀和与矩阵查询
  5. 前缀和+哈希表的组合技
  6. 实战技巧与总结

1. 什么是前缀和?

1.1 一维前缀和

前缀和数组 prefix 的每个元素表示原数组前 i 项的和:
p r e f i x [ i ] = n u m s [ 0 ] + n u m s [ 1 ] + ⋯ + n u m s [ i − 1 ] prefix[i] = nums[0] + nums[1] + \dots + nums[i-1] prefix[i]=nums[0]+nums[1]++nums[i1]
区间和计算
若求原数组区间 [L, R] 的和,只需:
s u m = p r e f i x [ R + 1 ] − p r e f i x [ L ] sum = prefix[R+1] - prefix[L] sum=prefix[R+1]prefix[L]
示例
原数组 [2, 3, -1, 4] 的前缀和为 [0, 2, 5, 4, 8],区间 [1,3] 的和为 8 - 2 = 6

1.2 二维前缀和

二维前缀和 prefix[i][j] 表示从 (0,0)(i-1,j-1) 的矩形区域和。
区域和计算
查询区域 (r1,c1)(r2,c2) 的和:
s u m = p r e f i x [ r 2 + 1 ] [ c 2 + 1 ] − p r e f i x [ r 1 ] [ c 2 + 1 ] − p r e f i x [ r 2 + 1 ] [ c 1 ] + p r e f i x [ r 1 ] [ c 1 ] sum = prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1] sum=prefix[r2+1][c2+1]prefix[r1][c2+1]prefix[r2+1][c1]+prefix[r1][c1]


2. 前缀和的应用场景

  • 高频查询区间和
  • 统计满足条件的子数组数量(如和为K、可被K整除的子数组)
  • 处理含负数的数组或需要取模的场景
  • 优化动态规划问题中的重复计算

3. 一维前缀和经典例题

例题1:和为K的子数组

问题:统计数组中连续子数组和为k的数量。
关键思路

  • 用哈希表记录前缀和出现的次数
  • 遍历时若发现 sum - k 在哈希表中,则累加次数

代码实现

def subarraySum(nums, k):prefix = {0: 1}  # 初始化:前缀和为0出现1次(空数组)sum_, count = 0, 0for num in nums:sum_ += numcount += prefix.get(sum_ - k, 0)  # 累加符合条件的子数组数量prefix[sum_] = prefix.get(sum_, 0) + 1  # 更新哈希表return count

例题2:和可被 K 整除的子数组

关键点

  • 计算前缀和模 K 的余数,利用同余定理
  • 处理负数余数:mod = (sum_ % K + K) % K

代码实现

def subarraysDivByK(nums, K):prefix = {0: 1}sum_, ans = 0, 0for num in nums:sum_ += nummod = (sum_ % K + K) % K  # 修正负数余数ans += prefix.get(mod, 0)prefix[mod] = prefix.get(mod, 0) + 1return ans

4. 二维前缀和与矩阵查询

例题3:二维区域和检索

核心思想

  • 构建二维前缀和数组时,利用容斥原理:
    p r e f i x [ i ] [ j ] = p r e f i x [ i − 1 ] [ j ] + p r e f i x [ i ] [ j − 1 ] − p r e f i x [ i − 1 ] [ j − 1 ] + m a t r i x [ i − 1 ] [ j − 1 ] prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i-1][j-1] prefix[i][j]=prefix[i1][j]+prefix[i][j1]prefix[i1][j1]+matrix[i1][j1]

代码实现

class NumMatrix:def __init__(self, matrix):m, n = len(matrix), len(matrix[0])self.prefix = [[0]*(n+1) for _ in range(m+1)]for i in range(m):for j in range(n):self.prefix[i+1][j+1] = self.prefix[i+1][j] + self.prefix[i][j+1] - self.prefix[i][j] + matrix[i][j]def sumRegion(self, r1, c1, r2, c2):return self.prefix[r2+1][c2+1] - self.prefix[r1][c2+1] - self.prefix[r2+1][c1] + self.prefix[r1][c1]

5. 前缀和+哈希表的组合技

例题4:连续数组

问题:找到含有相同数量0和1的最长子数组。
转化技巧:将0视为-1,问题转化为求和为0的最长子数组。

代码实现

def findMaxLength(nums):prefix = {0: -1}  # 记录前缀和首次出现的下标sum_, max_len = 0, 0for i, num in enumerate(nums):sum_ += 1 if num == 1 else -1if sum_ in prefix:max_len = max(max_len, i - prefix[sum_])else:prefix[sum_] = ireturn max_len

6. 实战技巧与总结

✅ 技巧清单

  1. 哈希表初始化:通常需加入 {0:1}{0:-1} 处理边界条件
  2. 负数取模:使用 (sum % K + K) % K 修正余数
  3. 二维前缀和公式:构建时注意容斥,查询时推导区域和公式
  4. 空间优化:二维前缀和可覆盖原数组(若允许修改)

🌟 总结

前缀和的核心是空间换时间,通过预处理数组优化区间查询。结合哈希表后,能高效解决子数组统计问题,尤其在处理负数、取模时展现强大能力。掌握前缀和,轻松应对LeetCode中80%的区间和问题!

练习

统计「优美子数组」


💬 互动

你在刷题时遇到过哪些前缀和相关的难题?欢迎留言讨论!
觉得本文有帮助?点赞⭐收藏🔖关注,支持作者持续创作!

关键字:商标转让费用_每日英语新闻_外贸网站如何推广优化_家电企业网站推广方案

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: