前缀和数组
定义
给定一个数组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
public static void Main()
{
int[] a = { 5, 4, 9, 2, 8, 7, 6 };
int k = 4;
int res = SubarraysDivByK(a, k);
Console.WriteLine(res);
}
public static int SubarraysDivByK(int[] A, int K)
{
int sum = 0;
int n = 0;
Dictionary<int, int> dic = new Dictionary<int, int>();
for (int i = 0; i < A.Length; i++)
{
sum += A[i];
int res = (sum % K + K) % K;
if (res == 0)
{
n++;
}
if (dic.Keys.Contains(res))
{
n += dic[res];
dic[res]++;
}
else
{
dic.Add(res, 1);
}
}
return n;
}
- 规律一
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个。
题目二
没找到。。。
.
.
.
.
.
.
.
.
.
>>转载请注明原文链接地址：前缀和与差分