前缀和 & 技巧小记

前缀和

• 子数组的元素之和：一维前缀和
• 子矩阵的元素之和：二维前缀和
• 前缀和 + 哈希表：寻找和为 target 的子数组

子数组的元素之和：一维前缀和

前缀和适用于快速、频繁地计算一个索引区间内的元素之和。

int res = 0;   // 存储区间[left，right]之和
for (int i = left; i <= right; i++) 
	res += nums[i];
return res;

但放在别的程序，往往需要多次计算区间 [left，right] 之和。

int preSum[nums.length + 1];
for (int i = 1; i < preSum.length; i++) 
	preSum[i] = preSum[i - 1] + nums[i - 1];
	
preSum[right + 1] - preSum[left];       // 每次调用这个即可

比如计算 nums[1，4] 元素和 = preSum[5] - preSum[1].

子矩阵的元素之和：二维前缀和

二维数组的子矩阵的元素之和，也能使用前缀和。

https://leetcode.cn/problems/range-sum-query-2d-immutable/solution/er-wei-qian-zhui-he-jian-dan-tui-dao-tu-sqekv/

任意子矩阵的元素和，都可转成周边4个矩阵的元素和：

preSum[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
	for (int j = 1; j <= n; j++) {
		// 前缀和计算每个矩阵 [0, 0] - [i, j] 的元素和
    	preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];   // 目标矩阵之和由四个相邻矩阵运算获得

int sumRegion(int x1, int y1, int x2, int y2) {    // 每次调用这个即可 
	return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];
}

前缀和 + 哈希表：寻找和为 target 的子数组

在 nums 中寻找和为 target 的子数组。

for (int i = 1; i < preSum.length; i++)
    for (int j = 0; j < i; j++) 
        if (preSum[i] - preSum[j] == target)   // 找到了

可以借助哈希表减少一个循环。

int hash[N];
for (int i = 0; i < preSum.length; i++)
	hash[preSum[i]] = i;

for (int i = 1; i < preSum.length; i++) 
    int book = target - preSum[i];
    if ( hash[book] ) // 找到了