文章目录 1 前缀和1.1 什么是前缀和？1.2 例题*1.3 前缀和+hash优化 2 差分2.1 什么是差分？2.2 例题
1 前缀和 1.1 什么是前缀和？
数学表达上他是：
假定有数列： a 0 , a 1 , a 2 . . . a i . . . a n a_0, a_1, a_2…a_i…a_n a0?,a1?,a2?…ai?…an?，则有前缀和 s 0 , s 1 , s 2 . . . s i . . . s n s_0, s_1, s_2…s_i…s_n s0?,s1?,s2?…si?…sn?，其中，
s 0 = a 0 s_0=a_0 s0?=a0?
s 1 = a 0 + a 1 s_1=a_0+a_1 s1?=a0?+a1?
s n = a 0 + a 1 + a 2 + a i + a n s_n=a_0+a_1+ a_2+a_i+a_n sn?=a0?+a1?+a2?+ai?+an?
作用：前缀和是一种重要的预处理，能大大降低查询的时间复杂度。
1.2 例题
以上都是概念，只看概念可能理解的不是很透彻，直接上例题：leetcode 560题
1 暴力解法： O ( n 3 ) O(n^3) O(n3)
略
2 前缀和方法： O ( n 2 ) O(n^2) O(n2)
int preSum[200001];int subarraySum(int* nums, int numsSize, int k){ // 入参检查 if (nums == NULL || numsSize == 0) { return 0; } // sumNums数组记录前缀和 preSum[0] = nums[0]; for (int i = 1; i < numsSize; i++) { preSum[i] = preSum[i – 1] + nums[i]; } int ans = 0; for (int i = 0; i < numsSize; i++) { for (int j = i; j < numsSize; j++) { // i ~ j 的连续子数组和用前缀和计算 // int subSum = i > 0 ? preSum[j] – preSum[i – 1] : preSum[j] 或下面这种形式均可; int subSum = preSum[j] – preSum[i] + nums[i]; if (subSum == k) { ans++; } } } return ans;} *1.3 前缀和+hash优化
C语言不想其他高级语言，对数据结构支撑并没有那么好，手撸复杂hash可能比较困难，幸好现在C语言支撑uthash，能够相对容易的使用hash，感兴趣的同学可以看一看，链接如下：https://blog.csdn.net/fan_h_l/article/details/107241520
还是以上题为例，前缀和+hash优化 的方法能使时间复杂度降低为 O ( n ) O(n) O(n)。由于官方解答叙述的已经很清晰，这里就不赘述了。其表述截图如下，详情键连接，官方还给出了动画。官方题解链接
3 前缀和+hash优化 ： O ( n ) O(n) O(n)
typedef struct Hash_ { int key; int value; UT_hash_handle hh;} Hash;int subarraySum(int* nums, int numsSize, int k){ // 入参检查 if (nums == NULL || numsSize == 0) { return 0; } Hash *head = NULL; Hash *zero = (Hash *)malloc(sizeof(Hash)); zero->key = 0; zero->value = 1; //初始和为0应存入 HASH_ADD_INT(head, key, zero); int ans = 0; int preSum = 0; for(int i=0; i<numsSize; i++){ preSum += nums[i]; Hash * find = NULL; //查找前置和为sum-k的点 int x = preSum – k; HASH_FIND_INT(head, &x, find); if(find!=NULL){ //前置和为sum-k的点,则可以满足其到当前索引i之间的子序列和为k ans += find->value; } Hash * temp = (Hash *)malloc(sizeof(Hash)); temp->key = preSum; temp->value = 1; //将当前i点的前置和sum查找并入表 find = NULL; HASH_FIND_INT(head, &preSum, find); if(find != NULL) { find->value = find->value + 1; } else { HASH_ADD_INT(head, key, temp); } } return ans;} 2 差分 2.1 什么是差分？
差分，是一种和前缀和相对的策略。
这种策略是，令 b i = a i ? a i ? 1 b_i = a_i – a_{i-1} bi?=ai??ai?1? ，即相邻两数的差。
易得对这个序列做一遍前缀和就得到了原来的序列。
2.2 例题
差分的应用上，可能需要稍微结合理论知识点想想，相信你做了一下两个典型题目，就会对差分有一个比较清晰的认知。
1094_拼车
1109_航班预定统计
C语言的解题代码，见我的github仓库。
个人觉得前期掌握前缀和和差分的以上知识，足以面对日常工作所需。
关于前缀和与差分的扩展可以参考了解：https://oi-wiki.org/basic/prefix-sum/。
58792073
