目录
1、模版
1.1【模版】一维前缀和
1.1.1 算法思想
1.1.2 算法代码
1.2【模版】二维前缀和
1.2.1 算法思想
1.2.2 算法代码
2、算法应用【leetcode】
2.1 题一:寻找数组的中心下标
2.1.1 算法思想
2.1.2 算法代码
2.2 题二:除自身以外数组的乘积
2.2.1 算法思想
2.2.2 算法代码
2.3 题三:和为k的子数组
2.3.1 算法思想
2.3.2 算法代码
2.4 题四:和可被k整除的子数组 ★★★蓝桥杯竞赛原题
2.4.1 算法思想
2.4.2 算法代码
2.5 题五:连续数组
2.5.1 算法思想
2.5.2 算法代码
2.6 题六: 矩阵区域和
2.6.1 算法思想
2.6.2 算法代码
1、模版
1.1【模版】一维前缀和
一维前缀和模版,通过下方例题讲解。
【模板】前缀和_牛客题霸_牛客网
1.1.1 算法思想
本题我们可以通过前缀和高效求解。
- 首先,预处理出一个前缀和数组,利用前缀和数组保存原数组数值之和。
- 接着,使用前缀和数组:dp[r] - dp[l-1] 得出arr[l~r]的和。
1.1.2 算法代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int q = in.nextInt();long[] arr = new long[n+1];for (int i = 1; i < arr.length; i++) {arr[i] = in.nextInt();}//预处理一个前缀和数组long[] dp = new long[n+1];for (int i = 1; i < arr.length; i++) {dp[i] = dp[i-1] + arr[i];}//使用前缀和数组while (q != 0) {int l = in.nextInt(), r = in.nextInt();System.out.println(dp[r] - dp[l - 1]);q--;}}
}
1.2【模版】二维前缀和
二维前缀和模版,我们同样通过例题讲解。
【模板】二维前缀和_牛客题霸_牛客网
1.2.1 算法思想
- 首先,同样预处理出前缀和矩阵,但是二维矩阵中存的数值为原数组arr[0,0]~arr[i,j]整个区域之和。通过画图我们可以得出公式。
- 接着,使用前缀和矩阵,因为我们求的是arr[x1][y1]~arr[x2][y2]之和,我们依然可以通过画图清晰明了的得出公式。
- 矩阵的下标依然是从1开始,为避免数组越界及计算错误,我们仍将i==0或者j==0位置的值设为0
1.预处理得出前缀和矩阵:
2.使用前缀和矩阵求值
1.2.2 算法代码
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), m = in.nextInt(), q = in.nextInt();int[][] arr = new int[n + 1][m + 1];for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {arr[i][j] = in.nextInt();}}//预处理一个前缀和矩阵//long防溢出long[][] dp = new long[n + 1][m + 1];for (int i = 1; i < n + 1; i++) {for (int j = 1; j < m + 1; j++) {dp[i][j] = dp[i][j - 1] + dp[i - 1][j] + arr[i][j] - dp[i - 1][j - 1];}}while (q != 0) {int x1 = in.nextInt(), y1 = in.nextInt();int x2 = in.nextInt(), y2 = in.nextInt();long val = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];System.out.println(val);q--;}}
}
注意:
模版仅仅为模版,并非前缀和算法的固定形式!!!算法的具体使用要就题论题,要学会举一反三!!!
2、算法应用【leetcode】
2.1 题一:寻找数组的中心下标
. - 力扣(LeetCode)
2.1.1 算法思想
- 已知中心下标左右两侧值的和相等,所以我们可以预处理一个前缀和数组和一个后缀和数组解决该题。
- 前缀和数组i位置处存的是arr[0]~arr[i-1]之和(不包含arr[i])
- 后缀和数组i位置处存的是arr[i-1]~arr[n-1]之和(不包含arr[i])
- 最后,同时遍历前后缀和数组,当前缀和数组f[i] == 后缀和数组g[i]时,则说明原数组i下标左右两侧值之和相等,i就为中心下标。
2.1.2 算法代码
class Solution {public int pivotIndex(int[] nums) {int len = nums.length;int[] f = new int[len];//前缀和数组int[] g = new int[len];//后缀和数组//预处理前缀和数组//f[0] = 0;下标0位置的左侧数据和为0for(int i = 1; i < len; i++) {f[i] = f[i - 1] + nums[i - 1];}//预处理后缀和数组//g[len - 1] = 0;下标len-1位置的右侧数据和为0for(int i = len - 2; i >= 0; i--) {g[i] = g[i + 1] + nums[i + 1];}for(int i = 0; i < len; i++) {if(f[i] == g[i]) return i;}return -1;}
}
2.2 题二:除自身以外数组的乘积
. - 力扣(LeetCode)
2.2.1 算法思想
本题思路与上题基本一致,只不过本题使用“积”的形式:
- 预处理一个前缀积和一个后缀积数组
- 前缀积数组i位置处存的是arr[0]~arr[i-1]之积(不包含arr[i])
- 后缀积数组i位置处存的是arr[i-1]~arr[n-1]之积(不包含arr[i])
- 同时遍历前后缀积数组,将两值相乘所得值赋给ret数组中,即为除自身以外的乘积
- 这里需要注意一个边界细节问题:在前缀积0下标处应存入的值为1;在后缀积n-1下标处应存入的值为1。
2.2.2 算法代码
class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[n];//预处理前缀积数组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 - 1 - 1; i >= 0; i--) {g[i] = g[i + 1] * nums[i + 1];}//使用前后缀积数组int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = f[i] * g[i];}return ret;}
}
2.3 题三:和为k的子数组
. - 力扣(LeetCode)
2.3.1 算法思想
2.3.2 算法代码
class Solution {public int subarraySum(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();//当前子数组的和就为kmap.put(0,1);int sum = 0;int ret = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];ret += map.getOrDefault(sum - k,0);map.put(sum, map.getOrDefault(sum,0) + 1);}return ret;}
}
2.4 题四:和可被k整除的子数组 ★★★蓝桥杯竞赛原题
. - 力扣(LeetCode)
2.4.1 算法思想
- 本题依然使用前缀和思想解题
- 解决本题,我们首先需要了解同余定理以及Java/C++在[负数%正数]结果的修正(均整理好放在了下图中)
- 依旧是查找以i结尾的子数组,当sum-x可被整除时,通过同余定理的转换,得到:查找在[0,i-1]区域中有多少个sum%k即有多少个可被整除的子数组
- 故,我们在哈希表中存储的并非前缀和,而是前缀和的余数
2.4.2 算法代码
class Solution {public int subarraysDivByK(int[] nums, int k) {int sum = 0;Map<Integer,Integer> map = new HashMap<>();int ret = 0;map.put(0,1);for(int i = 0; i < nums.length; i++) {sum += nums[i];//同余定理 && Java中[负数 % 正数]的校正(正确结果为正数,但Java或C++中得到的是负数)int val = (sum % k + k) % k;ret += map.getOrDefault(val, 0);map.put(val, map.getOrDefault(val, 0) + 1);}return ret;}
}
2.5 题五:连续数组
. - 力扣(LeetCode)
2.5.1 算法思想
- 哈希表+前缀和思想解题
- 将数组中的0元素转化为-1,进而将求0和1出现次数相同的最长子数组转变为求和为0的最长子数组
- 因为求最长的子数组,所以哈希表中不再存sum出现的次数,而是要存sum的下标
- 查找在[0,i-1]区域上的和为sum-0(sum)的子数组的末位置,得到的末位置+1就得到和为0的子数组的起始位置,计算得出长度,进而保留最长长度。
2.5.2 算法代码
class Solution {public int findMaxLength(int[] nums) {int sum = 0;Map<Integer,Integer> map = new HashMap<>();//和为0子数组前的和为sum-0的子数组map.put(0,-1);int max = 0;for (int i = 0; i < nums.length; i++) {//将为 0 -> -1//数组和为k -> 数组和为0sum += nums[i] == 0 ? -1 : 1;if (map.containsKey(sum)) {max = Math.max(max,i - (map.get(sum) + 1) + 1);}else {map.put(sum,i);}}return max;}
}
2.6 题六: 矩阵区域和
. - 力扣(LeetCode)
2.6.1 算法思想
该题需要使用二维前缀和思想:
- 利用上文二维前缀和模版题的思想,预处理出二维前缀和矩阵dp
- answer数组中元素的值,即为mat数组中的部分区域之和,可利用前缀和数组计算得出(使用前缀和数组计算得出区域之和)
- 本题需要额外注意mat、dp、answer数组之间的下标映射关系
- 其中,mat、answer数组矩阵下标是从0开始的,而我们预处理出的dp矩阵的有效数据是从1下标开始的
1.预处理出前缀和矩阵dp:
2.确定answer数组中元素数值:
3.确定下标映射关系:
2.6.2 算法代码
class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m = mat.length;int n = mat[0].length;int[][] dp = new int[m + 1][n + 1];for (int i = 1; i < m + 1; i++) {for (int j = 1; j < n + 1; j++) {dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];}}int[][] answer = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {//+1是为了处理下标映射关系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;answer[i][j] = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];}}return answer;}
}
END