目录
前缀和
一维前缀和模板
解法一：暴力解法（模拟）O(n·q)
解法二：前缀和（快速求出数组中某一个连续区间的和）O(q)
第一步：预处理出来一个前缀和数组
（dp [ i ] 表示[ 1, i ] 区间内所有元素的和，即dp[ i ]=dp[ i - 1 ]+arr[ i ] ）
第二步：使用前缀和数组
[ l ,r ]——>dp[ r ] - dp[ l - 1 ]
疑问（细节问题）：为什么下标从1开始计数？
答：为了处理边界情况（[ l ,r ]——>dp[ r ] - dp[ l - 1 ]当 l 为0时，不会越界）
二维前缀和模板
解法一：暴力解法（模拟）O(n·m·q)
解法二：前缀和 O(1)
1. 预处理出来一个前缀和矩阵
dp[ i ] [ j ] 表示：从[1，1]位置到[i , j]位置，这段区间里面所有元素的和
dp[ i ] [ j ]=A+B+C+D=(A+B)+(A+C)+D(该元素，由位置可得知)-A=dp[i-1] [ j ]+dp[ i ] [ j - 1]+arr[ i ] [ j ]-dp[i - 1] [j - 1]
2. 使用前缀和矩阵
[ x1 , y1 ]~[ x2 , y2 ]
D=(A+B+C+D)-(A+B)-(A+C)+A=dp[ x2 ] [ y2 ]-dp[x1-1] [y2]-dp[x2] [y1-1]+dp[x1-1] [y1-1]
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
//1. 读入数据
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] arr = new int[n + 1][m + 1]; //从1开始
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
arr[i][j] = in.nextInt();
}
}
//2. 预处理一个前缀和矩阵
long[][] dp = new long[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
}
}
//3. 使用前缀和数组
while (q > 0) {
int x1 = in.nextInt(), y1 = in.nextInt(), x2 = in.nextInt(), y2 = in.nextInt();
System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1
- 1]);
q--;
}
}
}寻找数组的中心下标
解法二：前缀和
前缀和数组：f[ i ]表示[0，i-1]区间所有元素的和，f[ i ]=f[ i - 1 ]+nums[ i - 1 ]
后缀和数组：g[ i ]表示[i+1，n-1]区间所有元素的和，g[ i ]=g[ i+1 ]+nums[ i+1 ]
f[ i ]==g[ i ]时返回 i
细节：f[0]=0,g[ n-1 ]=0
f从左往右，g从右往左
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] + nums[i - 1];
}
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;
}
}除自身以外数组的乘积
238. 除自身以外数组的乘积 - 力扣（LeetCode）
解法二：前缀积（用空间替换时间）
预处理前缀积以及后缀积
f[ i ]表示：[0，i-1]区间内所有元素的乘积
f[ i ]=f[i - 1]*nums[ i-1 ]
g[ i ]表示：[i+1，n-1]区间内所有元素的乘积
g[ i ]=g[ i+1 ]*nums[i+1]
return f[ i ]*g[ i ]
细节：f(0)=1，g(n-1)=1
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int[] g = new int[n];
int[] arr = new int[n];
f[0] = 1;
g[n - 1] = 1;
for (int i = 1; i < n; i++)
f[i] = f[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0; i--)
g[i] = g[i + 1] * nums[i + 1];
for (int i = 0; i < n; i++) {
arr[i] = f[i] * g[i];
}
return arr;
}
}和为 K 的子数组
解法一：暴力解法（枚举）
解法二：前缀和+哈希表
以 i 位置为结尾的所有的子数组
在[0，i-1]区间内，有多少个前缀和等于sum[ i ] - k
哈希表：<int，int>(<前缀和，次数>)
细节：
1. 前缀和加入哈希表的时机？
在计算 i 位置之前，哈希表里面只保存[0，i-1]位置的前缀和
2. 不用真的创建一个前缀和数组
用一个变量sum来标记前一个位置的前缀和即可
3. 如果整个前缀和等于k呢？
hash[0]=1
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0, 1);// hash[0]=1
int sum = 0, ret = 0;
for (int x : nums) {
sum += x;// 计算当前位置的前缀和
ret += hash.getOrDefault(sum - k, 0);// 统计结果
hash.put(sum, hash.getOrDefault(sum, 0) + 1);// 把当前的前缀和丢到哈希表里面
}
return ret;
}
}和可被 K 整除的子数组
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
某年蓝桥杯原题
补充知识：
1. 同余定理（a-b)➗p=k······0可得a%p=b%p
a-b=p*k
a=b+p*k
a%p=b%p2. [负数%正数] 的结果以及修正
负数%正数=负数【修正>】a%p+p【正负统一>】(a%p+p)%p
解法一：暴力枚举
解法二：前缀和+哈希表
在[0,i-1]区间内，找到有多少个前缀和的余数等于(sum%k+k)%k
哈希表<int,int> (<前缀和的余数，次数>)
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> hash = new HashMap<>();
hash.put(0 % k, 1);// 先存入一个0
int sum = 0, ret = 0;
for (int x : nums) {
sum += x;// 计算当前位置的前缀和
int r = (sum % k + k) % k;// 找到sum%k的个数，即为所求
ret += hash.getOrDefault(r, 0);// 统计结果
hash.put(r, hash.getOrDefault(r, 0) + 1);
}
return ret;
}
}class Solution {
public int subarraysDivByK(int[] nums, int k) {
int ret = 0, pre = 0;
int[] count = new int[k];
count[0] = 1;// 处理余数为0的特殊情况
for (int x : nums) {
pre = (pre + x % k + k) % k;// 调整余数为正
ret += count[pre];
count[pre]++;
}
return ret;
}
}连续数组
解法：前缀和+哈希表
转化：（将0转化为-1；在数组中，找出最长的子数组，使子数组中所有元素和为0）
和为k的子数组->和为0的子数组
解法：前缀和+哈希表
- 哈希表存什么？hash<int,int>（<前缀和，下标>）
- 什么时候存入哈希表？使用完之后丢进哈希表
- 如果有重复的<sum,i>，如何存？只保留前面的那一对<sum,i>
- 默认的前缀和为0的情况，如何存？hash[0]=-1
- 长度怎么算？
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0, -1);// 默认存在一个前缀和为0的情况
int sum = 0, ret = 0;
for (int i = 0; i < nums.length; i++) {
sum += (nums[i] == 0 ? -1 : 1);// 计算当前位置的前缀和
if (hash.containsKey(sum))
ret = Math.max(ret, i - hash.get(sum));
else
hash.put(sum, i);
}
return ret;
}
}矩阵区域和
解法：二位前缀和
dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i][j]
ret=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]
①ans[i][j]：
左上角-(x1,y1)->x1=max(0,i-k)+1;y1=max(0,j-k)+1
右下角-(x2,y2)->x2=min(m-1,i+k)+1;y2=min(n-1,j+k)+1
②下标映射关系：
下标从1开始
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;// m行n列
// 1. 预处理前缀和矩阵
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];//
}
}
// 2. 使用
int[][] ret = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x1 = Math.max(0, i - k) + 1, y1 = Math.max(0, j - k) + 1;
int x2 = Math.min(m - 1, i + k) + 1, y2 = Math.min(n - 1, j + k) + 1;
ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}
}
return ret;
}
}