一维数组中的前缀和
https://leetcode.com/problems/range-sum-query-immutable/description/
区域和检索
#include <stdio.h>
#include <stdlib.h>
// 定义 NumArray 结构体
typedef struct {
int* preSum; // 前缀和数组
} NumArray;
// 创建 NumArray 对象，并计算前缀和数组
NumArray* NumArrayCreate(int* nums, int numsSize) {
NumArray* obj = (NumArray*)malloc(sizeof(NumArray)); // 分配内存以存储 NumArray 结构体
obj->preSum = (int*)malloc(sizeof(int) * (numsSize + 1)); // 分配内存以存储前缀和数组
obj->preSum[0] = 0;
// 计算前缀和
for (int i = 1; i <= numsSize; i++) {
obj->preSum[i] = obj->preSum[i - 1] + nums[i - 1];
}
return obj;
}
// 计算闭区间 [left, right] 的累加和
int NumArraySumRange(NumArray* obj, int left, int right) {
return obj->preSum[right + 1] - obj->preSum[left];
}
// 释放内存
void NumArrayFree(NumArray* obj) {
free(obj->preSum); // 释放前缀和数组内存
free(obj); // 释放 NumArray 结构体内存
}
int main() {
// 测试用例
int nums[] = { 1, 2, 3, 4, 5 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
// 创建 NumArray 对象
NumArray* obj = NumArrayCreate(nums, numsSize);
// 计算闭区间的累加和
int sum = NumArraySumRange(obj, 1, 3);
printf("Sum Range = %d\n", sum);
// 释放内存
NumArrayFree(obj);
return 0;
}
看这个 preSum 数组，如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] -
preSum[1] 得出。
这样，sumRange 函数仅仅需要做⼀次减法运算，避免了每次进⾏ for 循环调⽤，最坏时间复杂度为常数
O(1)。
这个技巧在⽣活中运⽤也挺⼴泛的，⽐⽅说，你们班上有若⼲同学，每个同学有⼀个期末考试的成绩（满分
100 分），那么请你实现⼀个 API，输⼊任意⼀个分数段，返回有多少同学的成绩在这个分数段内。
那么，你可以先通过计数排序的⽅式计算每个分数具体有多少个同学，然后利⽤前缀和技巧来实现分数段查
询的 API
二维矩阵中的前缀和
https://leetcode.com/problems/range-sum-query-2d-immutable/description/
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int** preSum;
} NumMatrix;
// 创建 NumMatrix 对象，并计算前缀和矩阵
NumMatrix* NumMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
int m = matrixSize, n = *matrixColSize;
if (m == 0 || n == 0) return NULL;
// 分配内存以存储前缀和矩阵
NumMatrix* obj = (NumMatrix*)malloc(sizeof(NumMatrix));
obj->preSum = (int**)malloc(sizeof(int*) * (m + 1));
for (int i = 0; i <= m; i++) {
obj->preSum[i] = (int*)malloc(sizeof(int) * (n + 1));
}
// 计算前缀和矩阵
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
obj->preSum[i][j] = obj->preSum[i - 1][j] + obj->preSum[i][j - 1] + matrix[i - 1][j - 1] - obj->preSum[i - 1][j - 1];
}
}
return obj;
}
// 计算子矩阵 [x1, y1, x2, y2] 的元素和
int sumRegion(NumMatrix* obj, int x1, int y1, int x2, int y2) {
// 目标矩阵之和由四个相邻矩阵运算获得
return obj->preSum[x2 + 1][y2 + 1] - obj->preSum[x1][y2 + 1] - obj->preSum[x2 + 1][y1] + obj->preSum[x1][y1];
}
// 释放内存
void NumMatrixFree(NumMatrix* obj) {
for (int i = 0; i <= sizeof(obj->preSum) / sizeof(int*); i++) {
free(obj->preSum[i]);
}
free(obj->preSum);
free(obj);
}
int main() {
// 测试用例
int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
int* matrixPtr[3] = { matrix[0], matrix[1], matrix[2] };
// 创建 NumMatrix 对象
NumMatrix* obj = NumMatrixCreate(matrixPtr, 3, (int[]) { 3 });
// 计算子矩阵的元素和
int sum = sumRegion(obj, 0, 0, 1, 1);
printf("Sum Region = %d\n", sum);
// 释放内存
NumMatrixFree(obj);
return 0;
}
按照题⽬要求，矩阵左上角为坐标原点 (0, 0)，那么 sumRegion([2,1,4,3]) 就是图中红色的子矩阵，
你需要返回该子矩阵的元素和 8。
当然，你可以用一个嵌套for循环去遍历这个矩阵，但这样的话 sumRegion 函数的时间复杂度就⾼了，你算
法的格局就低了。
做这道题更好的思路和⼀维数组中的前缀和是⾮常类似的，如下图：
如果我想计算红色的这个子矩阵的元素之和，可以用绿色矩阵减去蓝色矩阵减去橙色矩阵最后加上粉色矩
阵，而绿蓝橙粉这四个矩阵有一个共同的特点，就是左上角就是 (0, 0) 原点。
那么我们可以维护一个二维 preSum 数组，专门记录以原点为顶点的矩阵的元素之和，就可以用几次加减运
算算出任何一个子矩阵的元素和
和为k的子数组
#include <stdio.h>
#include <stdlib.h>
int subarraySum(int* nums, int numsSize, int k) {
// 构造前缀和数组
int* preSum = (int*)malloc(sizeof(int) * (numsSize + 1));
preSum[0] = 0;
for (int i = 0; i < numsSize; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
int res = 0;
// 穷举所有子数组
for (int i = 1; i <= numsSize; i++) {
for (int j = 0; j < i; j++) {
// 子数组 nums[j..i-1] 的元素和
if (preSum[i] - preSum[j] == k) {
res++;
}
}
}
free(preSum);
return res;
}
int main() {
int nums[] = { 1, 2, 3, 4, 5 };
int k = 3;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int count = subarraySum(nums, numsSize, k);
printf("Number of subarrays with sum %d = %d\n", k, count);
return 0;
}
这个解法的时间复杂度 O(N^2) 空间复杂度 O(N)，并不是最优的解法。不过通过这个解法理解了前缀和数
组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低。
注意前面的解法有嵌套的 for 循环：
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (preSum[i] - preSum[j] == k)
res++;
第二层 for 循环在干嘛呢？翻译一下就是，在计算，有几个 j 能够使得 preSum[i] 和 preSum[j] 的差为
k。毎找到一个这样的 j，就把结果加一。
我们可以把 if 语句里的条件判断移项，这样写：
if (preSum[j] == preSum[i] - k)
res++;
优化的思路是：我直接记录下有几个 preSum[j] 和 preSum[i] - k 相等，直接更新结果，就避免了内层
的 for 循环。我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。(看不懂版）
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int key;
int value;
} Entry;
typedef struct {
Entry* entries;
int size;
int capacity;
} HashMap;
HashMap* createHashMap(int capacity) {
HashMap* hashMap = (HashMap*)malloc(sizeof(HashMap));
hashMap->entries = (Entry*)calloc(capacity, sizeof(Entry));
hashMap->size = 0;
hashMap->capacity = capacity;
return hashMap;
}
void put(HashMap* hashMap, int key, int value) {
int index = key % hashMap->capacity;
while (hashMap->entries[index].value != 0) {
index = (index + 1) % hashMap->capacity;
}
hashMap->entries[index].key = key;
hashMap->entries[index].value = value;
hashMap->size++;
}
int getOrDefault(HashMap* hashMap, int key, int defaultValue) {
int index = key % hashMap->capacity;
while (hashMap->entries[index].value != 0 && hashMap->entries[index].key != key) {
index = (index + 1) % hashMap->capacity;
}
if (hashMap->entries[index].value != 0) {
return hashMap->entries[index].value;
}
return defaultValue;
}
int subarraySum(int* nums, int numsSize, int k) {
int n = numsSize;
HashMap* preSum = createHashMap(n + 1);
put(preSum, 0, 1);
int res = 0, sum0_i = 0;
for (int i = 0; i < n; i++) {
sum0_i += nums[i];
int sum0_j = sum0_i - k;
res += getOrDefault(preSum, sum0_j, 0);
int freq = getOrDefault(preSum, sum0_i, 0);
put(preSum, sum0_i, freq + 1);
}
free(preSum->entries);
free(preSum);
return res;
}
int main() {
int nums[] = { 1, 1, 1 };
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
int count = subarraySum(nums, numsSize, k);
printf("Number of subarrays with sum %d = %d\n", k, count);
return 0;
}
这样，就把时间复杂度降到了 O(N)，是最优解法了。
前缀和技巧就讲到这⾥，应该说这个算法技巧是会者不难难者不会，实际运⽤中还是要多培养⾃⼰的思维灵
活性，做到⼀眼看出题⽬是⼀个前缀和问题。