04-前缀和

算法原理

当需要快速地求出一段连续数组区间的和时候，就需要使用它了

1. 把数据经行预处理，先生成 dp 数组，它的长度是原数组 arr（令第一个数据的下标为 1） 的总长度 + 1
2. 接着把 dp 第一个数据设置为 0, **dp[i] 表示 [1, i] 这个区间内 arr 数据之和（**求和可以使用 dp[i] = dp[i - 1] + arr[i] 来计算）
3. 如果要算出 [n, m] 区间内的值，那么只需要计算 dp[m] - dp[n - 1] 即可

题目

NC35. 搜索插入位置

思路就是和上面“算法原理”一样

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    // 注意 hasNext 和 hasNextLine 的区别
    while (in.hasNextInt()) { // 注意 while 处理多个 case
        int len = in.nextInt();
        int q = in.nextInt();
        long[] dp = new long[len + 1]; // 设置为 long 防止越界
        // 处理 dp 从下标 1 开始
        for(int i = 1; i < dp.length; i++) {
            dp[i] = dp[i - 1] + in.nextInt();
        }

        // 计算结果
        for (int i = 0; i < q; i++) {
            System.out.println(-dp[in.nextInt() - 1] + dp[in.nextInt()]);
        }
    }
}

DP35 【模板】二维前缀和

这是是一个二维的前缀和，思路和之前的一样：先求 dp 然后再计算（建议通过画图来理解）

1. 求dp: dp[i, j] 它是表示[1, 1] 到 [i, j] 这个区间内的和。它是可以通过 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j] 来求出相关的值
2. 计算：通过 dp 来计算，可以通过 dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] 来求出题目中的结果

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
	int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();
	long[][] dp = new long[n + 1][m + 1];

	for (int i = 1; i < dp.length; i++) {
		for (int j = 1; j < dp[i].length; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + in.nextInt();
		}
	}

	// 注意 hasNext 和 hasNextLine 的区别
	while (in.hasNextInt()) { // 注意 while 处理多个 case
		int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
		System.out.println(dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1]);
	}
}

LC724. 寻找数组的中心下标

这个使用两个数组来表示，一个是前缀和，一个是后缀和

其中 f 是前缀和，g 是后缀和， f[i] 表示 [0, i - 1] 区间内的值， g[i] 表示 [i + 1, n - 1] 区间的值

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int pivotIndex(int[] nums) {
	int n = nums.length;
	// f 表示从前往后的 dp 数组， g 是表示从后往前的
	// f[i] 表示 [0, i - 1] 区间内的值， g[i] 表示 [i + 1, n - 1] 区间的值
	int[] f = new int[n], g = new int[n];
	
	// 初始化 f
	for (int i = 1; i < n; i++) {
		f[i] = nums[i - 1] + f[i - 1];
	}

	// 初始化 g
	for (int i = n - 2; i >= 0; i--) {
		g[i] = g[i + 1] + nums[i + 1];
	}

	// 判断
	for (int i = 0; i < n; i++) {
		if (f[i] == g[i]) return i;
	}
	return -1;
}

---

当然这道题目也可以不用前缀和思想，先求总和，然后根据总和算出左右区间，那么就解决这个题目

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int pivotIndex(int[] nums) {
	// 先求和
	int n = nums.length;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += nums[i];
	}

	// 定义左边的和和右边的和
	int i = 0, sumLeft = 0, sumRight = sum - nums[i];
	for (; i < n - 1; i++) {
		if (sumLeft == sumRight) return i;
		sumLeft += nums[i];
		sumRight -= nums[i + 1];
	}

	return sumLeft == sumRight ? n - 1 : -1;
}

LC238. 除了自身以外数组的乘积

这道题和上面的 LC724. 寻找数组的中心下标 思路一样，只不过把求和变为求积了而已。

f[i] 表示 [0, i - 1] 区间内的积， g[i] 表示 [i + 1, n - 1] 区间的积

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int[] productExceptSelf(int[] nums) {
	int n = nums.length;
	// 先算出前缀 和 后缀
	int[] f = new int[n], g = new int[n];

	// f[i] 表示 [0, i - 1] 这个区间的积 g[i] 表示 [i + 1, n - 1] 的数量积
	f[0] = 1;
	for (int i = 1; i < n; i++) {
		f[i] = f[i - 1] * nums[i - 1];
	}

	g[n - 1] = 1;
	for (int i = n - 2; i >= 0; i--) {
		g[i] = g[i + 1] * nums[i + 1];
	}

	int[] result = new int[n];

	for(int i = 0; i < n; i++) {
		result[i] = f[i] * g[i];
	}

	return result;
}

LC560. 和为 K 的子数组

这题是使用 前缀和+哈希表 来解决这个问题

1. 先求出 [0, i] 区间内的和 sum
2. 把问题转换一下，把 找到 [n, i] 区间内的和为 k 这个问题变为 找到 [0, n - 1] 这个区间内的和为 sum - k

   为什么这样弄？因为 [0, n - 1] 也是前缀和，可以复用之前的

3. 可以使用哈希表来统计之前前罪和为 sum - k 的出现次数

细节考虑：

1. 哈希表是不能一口气全部求出来，不然会重复。因为我们是求 i 位置之前的和为 sum - k 的前缀和，而不是求全部的
2. 需要在哈希表里面添加前缀和为 0 的情况，因为需要考虑到 [0, i] 的 sum 刚好等于 k 的情况
3. 前缀和可以不需要数组表示，因为之前的前缀和是存在哈希表里面了，不需要重新遍历一次前缀和数组

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int subarraySum(int[] nums, int k) {
	// sum 表示 [0, i] 区间内的和
	int sum = 0, n = nums.length;
	// key 表示前缀和 value 表示前缀和个数
	HashMap<Integer, Integer> hash = new HashMap<>();
	hash.put(0, 1); // 为了防止 [0, i] 这个区间内的和刚好为 k 

	int result = 0;
	// 通过计算 sum - k 的个数来求出 i 位置的符合条件的个数
	for (int i = 0; i < n; i++) {
		sum += nums[i];
		result += hash.getOrDefault(sum - k, 0);
		hash.put(sum, hash.getOrDefault(sum, 0) + 1);
	}

	return result;
}

LC974. 和可被 K 整除的子数组

这个题目很像 LC560. 和为 K 的子数组 这个题目，它们都是求前 n 个和，然后求个数

思路：

1. 先算出 sum 它表示 [0, i] 区间内的和
2. 根据题意发现，想要求出 m % k == 0 的条件，可以转变为 (sum - n) % k == 0 这个条件，再根据同余定理，得出 sum % k == n % k 这个条件
3. 最后发现在哈希表内存储前缀和的余数即可

这个题目需要有两个格外的知识

1. 知道同余定理公式

$$(a-b)÷p=k...0\Rightarrow a\mathrm{\%}p=b\mathrm{\%}p\text{ ?}$$

2. Java, C++ 余数变为正数的公式：((sum % k) + k) % k

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int subarraysDivByK(int[] nums, int k) {
	// sum 是表示 [0, i] 区间元素之和
	int sum = 0, n = nums.length;

	// map 的 key 是存储 sum % k 的值，不过需要注意的是要变为正数
	// m 是 [xxx, i - 1] 区间的和， n 是 [0, xxx - 1] 区间的和 
	// m % k == 0 -> (sum - n) % k == 0 -> sum % k == n % k -> 因此 key 是余数
	int result = 0;
	Map<Integer, Integer> map = new HashMap<>();
	map.put(0, 1); // 必须要有这个，防止刚好 sum % k 为 0 的情况
	for(int num : nums) {
		sum += num;
		int key = ((sum % k) + k) % k; // 确保 key 是正数
		result += map.getOrDefault(key, 0);
		map.put(key, map.getOrDefault(key, 0) + 1);
	}
	return result;
}

LC525. 连续数组

这个题目很像 LC560. 和为 K 的子数组 这个题目，把 0 转为 -1 ，然后求和为 0 的最长子区间，接着只需要再处理一系列细节即可

1. Hash 表里面，K V 分别表示什么？

   V 是表示下标，K 是 [0, Hash[K]] 区间内的和

2. 获取到重复的 K, 应该如何解决呢？

   直接忽略，因为题目是求最长的长度，而不是最短的长度

3. 什么时候把值添加到 Hash 表中

   在处理完一轮完之后再添加，防止干扰之前的内容

4. 默认的前缀和为 0 的情况下如何处理呢？

   因为 V 存储的是下标，而最开始和为 0 的下标可以看为 -1, 因此需要把 [0, -1] 添加在 Hash 表内，考虑到 nums 为 [0, 1] 这样类似的情况

5. 长度怎么算？

   建议通过画单元格来理解。通过 i - hash[sum] 来算出来

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int findMaxLength(int[] nums) {
	// 把 0 看为 -1 然后转换为求和为 0 的连续区间
	int n = nums.length;
	for (int i = 0; i < n; i++) {
		if (nums[i] == 0) nums[i] = -1;
	}

	// hash 表里面的 v 表示是当前的下标, k 是表示 [0, hash[k]] 和
	HashMap<Integer, Integer> hash = new HashMap<>();
	hash.put(0, -1); // 需要考虑到 [0, 1] 这样类似的情况
	// sum 表示 [0, i] 区间内的值
	int sum = 0, result = 0;
	for (int i = 0; i < n; i++) {
		sum += nums[i];
		// 获取最长的长度，如果没有找到，就要返回 i 使相减的结果为 0
		result = Math.max(i - hash.getOrDefault(sum, i), result);
		// 如果重复，不需要更新，因为题目要求是获取最长的长度
		if (!hash.containsKey(sum)) hash.put(sum, i);
	}

	return result;
}

LC1314. 矩阵区域和

这个就需要参考到求二维数组的前缀和了

dp 求和

前缀和-二维前缀和-dp求和

但是在这个题目中，需要考虑到下标映射的情况，因为这个题目是从 0 开始的，而不是从 1 开始

计算区间和

前缀和-二维前缀和-计算区间和

思考：为什么 x2/y2 不需要减一而 x1/y1 却需要呢？

因为题目是需要计算 x1/y1 - x2/y2 这个区间内的值，它们是包含的在内的

步骤

1. 使用二维前缀和来解决
2. 需要考虑映射情况，之前的二维前缀和是从 1 开始的，而这个题目是从 0 开始的
3. 需要考虑边界情况

用例 1/1

步骤： 0 / 0

当前动作：等待输入...

public int[][] matrixBlockSum(int[][] mat, int k) {
	// 计算二维前缀和（注意下标映射）: dp 是从 1 开始的，而 mat 是从 0 开始的
	int rowN = mat.length, colN = mat[0].length;
	int[][] dp = new int[rowN + 1][colN + 1];
	for (int i = 1; i < rowN + 1; i++) {
		for (int j = 1; j < colN + 1; j++) {
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
		}
	}

	int[][] result = new int[rowN][colN];
	// 计算矩形的左上角坐标和右下角坐标
	for (int i = 0; i < rowN; i++) {
		for (int j = 0; j < colN; j++) {
			// 需要考虑映射: dp 是比 mat 多 1, 因此只需要加 1 就可以了
			int x1 = Math.max(0, i - k) + 1, y1 = Math.max(0, j - k) + 1;
			int x2 = Math.min(rowN - 1, i + k) + 1, y2 = Math.min(colN - 1, j + k) + 1;

			// 计算
			result[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
		}
	}

	return result;
}