C#/.Net

前缀和与差分

前缀和数组

定义

给定一个数组A[n],则其前缀和数组有B[m]=A[0]+A[1]+…+A[m]。

例:

A[]={5,6,7,9,3,4}

B[]={5,11,18,27,30,34}

B[0]=A[0]

B[1]=A[0]+A[1]

B[2]=A[0]+A[1]+A[2]

B[3]=A[0]+A[1]+A[2]+A[3]

B[4]=A[0]+A[1]+A[2]+A[3]+A[4]

B[5]=A[0]+A[1]+A[2]+A[3]+A[4]+A[5]

差分数组

定义

给定数组A[n],则其差分数组B[n]=A[n]-A[n-1] n>0,且B[0]=A[n]-0。

且有一下特性:

  • 特性一

A[n]=B[0]+B[1]+…+B[n]

A[n]=(A[0]-0)+(A[1]-A[0] )+(A[2]-A[1] )+…+A[n]-A[n-1]

A[n]=A[n]

  • 特性二

B[n]的前缀和数组sumB[n]=B[0]+B[1]+…+B[n]

由特性一可得sumb[n]=(A[0]-0)+(A[1]-A[0] )+(A[2]-A[1] )+…+A[n]-A[n-1] =A[n]

即当B[n]为A[n]的差分数组时,A[n]为B[n]的前缀和数组。

适用场景

主要可以应用到快速处理区间加减操作、查询区间和问题

比如,

1.给定A[],在区间[i,j]的所有数组均加value,求操作后的A[]。

2.给定A[],求区间[i,j]的和,

题目一

  • 给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。LeetCode

  • 示例:

    输入:A = [4,5,0,-2,-3,1], K = 5
    输出:7
    解释:
    有 7 个子数组满足其元素之和可被 K = 5 整除:
    [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

  • 提示:

    1 <= A.length <= 30000
    -10000 <= A[i] <= 10000
    2 <= K <= 10000

  • 规律一

B[3]%4==0,B[4]%4==0,这个好理解,A[0,1,2,3]与A[0,1,2,3,4]即为符合题目要求的数组。

由上述可得:余数0出现2次,计2。

  • 规律二

B[0]%4==1,B[0]%4==1,B[6]%4==1;

B[0]与B[1]的差为A[1]=4

B[0]与B[6]的差为A[1,2,3,4,5,6]=36

当某一余数重复出现时,则必有连续数组符合题目要求。

规律为:当余数x出现的次数为n时,符合题目要求的数组数量等于1+2+3+…+(n-1)

余数0出现2次,计1;

余数1出现3次,计3;

  • 由上述可得:

合计符合题目要求数组为6个。

题目二

没找到。。。

.
.
.
.
.
.
.
.
.

【本文章出自NM1024.com,转载请注明作者出处。】

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据