【算法】【优选算法】前缀和（上）
目录
- 一、前缀和算法简介
- 1.1 一维前缀和模版
- 1.2 二位前缀和模版
- 二、【模板】前缀和
- 2.1 前缀和
- 2.2 暴力枚举
- 三、【模板】⼆维前缀和
- 3.1 前缀和
- 3.2 暴力枚举
- 四、724.寻找数组的中⼼下标
- 4.1 前缀和
- 4.2 暴力枚举
- 五、238.除⾃⾝以外数组的乘积
- 5.1 前缀和
- 5.2 暴力枚举
一、前缀和算法简介
前缀和算法：就是快速求取数组中一段连续区间的和的算法。
1.1 一维前缀和模版
- 预处理一个前缀和数组dp[ ]：数组中的元素dp[ i ]表示从原数组[ 1 , i ]的和。
- 所以 dp[ i ] = dp [ i - 1 ] + arr[ i ]
- 要求区间[ l , r ] 的和，就是dp[ r ] - dp[ l - 1 ]
1.2 二位前缀和模版
- 预处理一个前缀和矩阵：dp[ i ][ j ]的含义就是从原数组(1,1)到(i , j)的和。
- 我们求dp[ i ][ j ] : dp[ i ][ j ] = dp[ i - 1][ j ] + dp[ i ][ j - 1] - dp[ i - 1][ j - 1] + arr[ i ][ j ]。就相当于下图的：B区 + C区 - A区 + arr[ i ][ j ]
- 求(x1,y1)到(x2,y2)的和：dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]。对应下图就是: B区 - C区 - D区 + A区
二、【模板】前缀和
题目链接：【模板】前缀和
题目描述：
题目解析：
- 给我们一个数组从1下标开始给数组元素，让我们打印出要求的每一段子数组和。
2.1 前缀和
解题思路：
- 我们使用一个一个dp数组来表示每一段数组的和。即dp[ i ] 就表示原数组中1到 i 下标元素的和。
- 求l到r的元素和，直接就是dp[ r ] - dp[ l - 1]。
- 由于可能求0到2这种 l 等于0的子数组，所以我们将dp数组的长度置为n+1，并且dp[ 0 ] = 0。
- 细节问题：由于元素值是比较大的，所以我们求和是有可能超出int范围的，所以dp数组要使用long类型。
解题代码：
//时间复杂度：O(n+q)
//空间复杂度：O(n)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
long[] dp = new long[n+1];
for(int i = 1; i <= n; i++) {
dp[i] = dp[i-1] + (long)in.nextInt();
}
while(q > 0) {
int l = in.nextInt();
int r = in.nextInt();
System.out.println(dp[r] - dp[l-1]);
q--;
}
}
}
2.2 暴力枚举
解题思路：
- 直接先将数组存下来，在通过 l 和 r来遍历求和。
- 会超时。
解题代码：
//时间复杂度：O(n*q)
//空间复杂度：O(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
int[] arr = new int[n+1];
for(int i = 1; i <= n; i++) {
arr[i] = in.nextInt();
}
while(q > 0) {
int l = in.nextInt();
int r = in.nextInt();
long ret = 0;
for(int i = l; i <= r; i++) {
ret += arr[i];
}
System.out.println(ret);
q--;
}
}
}
三、【模板】⼆维前缀和
题目链接：【模板】⼆维前缀和
题目描述：
题目解析：
- 给我们一个二维数组，以(1,1)开始作为数组头。
- 让我们返回给的两个下标包围的元素的和，例如给(1,1)和(2,3)那么和就是arr[1,1]+arr[1,2]+arr[1,3]+arr[2,1]+arr[2,2]+arr[2,3]。
- 我们使用一个表示前缀和的数组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 ]
- 求(x1 , y1)到(x2 , y2)的和就是dp[x2][y2] - dp[x1 - 1][ y2] - dp[x2][ y1 - 1] + dp[x1 - 1][y1 - 1]
- 由于可能求0到2这种 l 等于0的子数组，所以我们将dp数组的长度置为[n+1][m+1]，并且dp[ 0 ] = 0。
- 细节问题：由于元素值是比较大的，所以我们求和是有可能超出int范围的，所以dp数组要使用long类型。
3.1 前缀和
//时间复杂度：O(n*m + q)
//空间复杂度：O(n*m)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
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][j-1] + dp[i-1][j] - dp[i-1][j-1] + in.nextInt();
}
}
while(q > 0) {
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
System.out.println(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]);
q--;
}
}
}
3.2 暴力枚举
解题思路：
- 将数组保存下来，按要求求和即可。
- 会超时。
//时间复杂度：O(n*n*q)
//空间复杂度：O(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
long[][] arr = new long[n+1][m+1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
arr[i][j] = in.nextInt();
}
}
while(q > 0) {
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
long ret = 0;
for(int i = x1; i <= x2; i++) {
for(int j = y1; j <= y2; j++) {
ret += arr[i][j];
}
}
System.out.println(ret);
q--;
}
}
}
四、724.寻找数组的中⼼下标
题目链接：724.寻找数组的中⼼下标
题目描述：
题目解析：
- 就是返回当前下标元素，第一个满足左边元素和与右边元素和相等的下标。
- 数组头左边和为0，数组尾右边和为0。
- 如果没有返回-1。
4.1 前缀和
解题思路：
- 直接套用一维前缀和模版。
- 注意现在的原数组是从0下标开始的，为了避免边界考虑，所以前缀和数组还是从1开始，只不过dp[ i ] = dp[ i - 1] + nums[ i - 1]。
- 因为不包含i下标的元素，所以判断条件dp[i-1] == dp[n] - dp[i]，
- dp[ i ]表示的是原数组中[ 0 , i - 1]的和，所以最后返回的也是i - 1
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] dp = new int[n+1];
for(int i = 0; i < n; i++) {
dp[i+1] = dp[i] + nums[i];
}
for(int i = 1; i < n+1; i++) {
if(dp[i-1] == dp[n] - dp[i]) return i-1;
}
return -1;
}
}
4.2 暴力枚举
解题思路：
- 直接先将数组中所有元素和求出来，
- 再遍历数组，用变量表示当前下标前的元素的和，
- 判断是否符合条件即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int sum = 0;
for(int i = 0; i < n; i++) {
sum += nums[i];
}
int preSum = 0;
for(int i = 0; i < n; i++) {
if(i != 0) preSum += nums[i-1];
if(preSum == sum - preSum - nums[i]) return i;
}
return -1;
}
}
五、238.除⾃⾝以外数组的乘积
题目链接：238.除⾃⾝以外数组的乘积
题目描述：
题目解析：
- 求数组中，除去该元素的剩下元素的乘积，存入结果数组中。
- 不用担心超出int范围。
5.1 前缀和
解题思路：
- 使用一个dp1数组，表示前缀积，从[0, i - 1]的乘积。
- 所以dp[ i ] = dp[ i - 1] * nums[ i - 1]。
- 使用一个dp2数组，表示后缀积，从[ i + 1 , n - 1]的乘积。
- 所以dp[ i ] = dp[ i + 1] * nums[ i + 1]。
- 最后放入结果数组中时: ret[ i ] = dp1[ i ] * dp2[ i ]。
- 细节处理：
-
- 初始化dp1的时候dp1[ 0 ] 会越界，先直接赋值为nums[ 0 ]；
-
- 初始化dp2的时候dp2[ n - 1 ] 会越界，先直接赋值为nums[ n - 1 ]；
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
//前缀积
int[] dp1 = new int[n];
for(int i = 0; i < n; i++) {
if(i == 0) {
dp1[i] = 1;
continue;
}
dp1[i] = dp1[i-1] * nums[i - 1];
}
//后缀积
int[] dp2 = new int[n];
for(int i = n-1; i >=0; i--) {
if(i == n-1) {
dp2[i] = 1;
continue;
}
dp2[i] = dp2[i+1] * nums[i+1];
}
//结果数组
int[] ret = new int[n];
for(int i = 0; i < n; i++) {
ret[i] = dp1[i] * dp2[i];
}
return ret;
}
}
5.2 暴力枚举
解题思路：
- 直接遍历数组，在求积即可。
- 会超时。
解题代码：
//时间复杂度：O(n^2)
//空间复杂度：O(1)
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] ret = new int[n];
for(int i = 0; i < n; i++) {
ret[i] = 1;
for(int j = 0; j < n; j++) {
if(i != j) ret[i] *= nums[j];
}
}
return ret;
}
}