企业官网建设流程全解析

目录

前言

一、一维前缀和

1. 核心原理

2.适用场景

3、典型例题

（1）和为 k 的连续子数组个数。（前缀和+哈希表）

（2）连续子数组的最大子数组和

（3）连续01最长子串，要求01数量相同

（4）分割数组使两侧和相等

二、二维前缀和（子矩阵求和）

1. 核心原理

2、适用场景

3、典型例题

总结

前言

前缀和是蓝桥杯省赛、国赛高频考点，核心作用是O (1) 时间快速求解区间和，把暴力 O (n)、O (nm) 的查询优化到常数时间，是处理数组、矩阵区间求和问题的最优解。

一、一维前缀和

1. 核心原理

• 定义：preSum[i]表示原数组前 i 个元素的和（preSum[0] = 0，避免边界判断）
• 注意：数组第 i 个数对应数组下标 i-1
• 公式：
  1. 预处理：preSum[i] = preSum[i-1] + nums[i-1]
  2. 区间和：nums[l ... r] 和 = preSum[r] - preSum[l-1]
• 时间复杂度：预处理 O (n)，查询 O (1)

2.适用场景

• 多次查询数组连续子区间和
• 子数组求和、统计和为 k 的子数组、最大子段和

Java代码示例

public static void main(String[] args) { // 原数组（下标从0开始） int[] nums = {1, 2, 3, 4, 5}; int n = nums.length; // 1. 构建前缀和数组（长度n+1，preSum[0]=0） int[] preSum = new int[n + 1]; for (int i = 1; i <= n; i++) { preSum[i] = preSum[i - 1] + nums[i - 1]; } // 2.例：求nums数组（元素2,3,4）的和 int sum = preSum[4] - preSum[1]; }

或者

int[] nums = {1,2,3,4}; int n = nums.length; int[] preSum = new int[n + 1]; // 构建前缀和 for (int i = 0; i < n; i++) { preSum[i + 1] = preSum[i] + nums[i]; }

3、典型例题

（1）和为 k 的连续子数组个数。（前缀和+哈希表）

核心就是看有多少对（i，j）满足： preSum[j] - preSum[i]=k--->转化为：求preSum[i]的个数

• 用前缀和算区间和
• 用哈希表记录前缀和出现次数
• 每一步查：preSum - k 是否出现过
• 出现过几次，就有几个和为 k 的子数组

public static int subarraySum(int[] nums, int k) { // key = 前缀和，value = 这个前缀和出现的次数 Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); // 必须放：前缀和为 0 出现 1 次 int preSum = 0; int count = 0; for (int num : nums) { preSum += num; // 计算当前前缀和 // 核心：如果 preSum - k = 较小的那个前缀和（如果已经存入哈希表，直接加上它的个数=满足要求对数） if (map.containsKey(preSum - k)) { count += map.get(preSum - k); } // 把当前前缀和放进 map map.put(preSum, map.getOrDefault(preSum, 0) + 1); } return count; }

（2）连续子数组的最大子数组和

思路：每次求区间子数组和时，需要更新最小前缀和的值，使得减数尽可能小，差才尽可能大

public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] pre = new long[n+1]; for(int i=1;i<=n;i++){ pre[i]=pre[i-1]+sc.nextInt(); } long minPre = pre[0], ans = Long.MIN_VALUE; for(int i=1;i<=n;i++){ ans = Math.max(ans,pre[i]-minPre); minPre = Math.min(minPre,pre[i]); } System.out.println(ans); }

（3）连续01最长子串，要求01数量相同

转换：0变-1，求最长子数组和为0的长度

用一个哈希表记录前缀和大小和对应下标索引，如果有相同大小的前缀和，做差之后区间和就是0，因此记录这段区间长度，最后取最大区间长度。

public static void main(String[] args) { String s = new Scanner(System.in).next(); Map<Integer,Integer> pos = new HashMap<>(); pos.put(0,0); int sum=0,maxLen=0; for(int i=1;i<=s.length();i++){ char c = s.charAt(i-1); sum += c=='0'?-1:1; if(pos.containsKey(sum)){ maxLen=Math.max(maxLen,i-pos.get(sum)); }else pos.put(sum,i); } System.out.println(maxLen); }

（4）分割数组使两侧和相等

思路：前缀和思想，遍历前缀和数组如果pre[i]==pre[n]-pre[i] ，说明 i 是分割位

public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long[] pre = new long[n+1]; for(int i=1;i<=n;i++){ pre[i]=pre[i-1]+sc.nextInt(); } int count=0; for(int i=1;i<n;i++){ if(pre[i]==pre[n]-pre[i]){ count++; } } System.out.println(count); }

变式：分割数组，使得每个子数组和相等，问有几种分割方案

暗含条件：子数组必须连续（因此顺序遍历数组）

解题思路

1. 先计算数组总和total，如果total % k != 0→ 直接无法分割
2. 目标子数组和target = total / k
3. 遍历数组累加，每达到target就分割一次，重置累加和
4. 最终统计分割次数是否等于k

public static List<List<Integer>> splitEqualSum(int[] nums, int k) { //用于存储分割后的结果 List<List<Integer>> result = new ArrayList<>(); int totalSum = Arrays.stream(nums).sum(); // 边界条件1：总和无法被k整除，直接返回空 if (totalSum % k != 0) { return result; } int target = totalSum / k; // 每个子数组的目标和 int currentSum = 0; List<Integer> temp = new ArrayList<>(); for (int num : nums) { currentSum += num; temp.add(num); // 达到目标和，完成一次分割 if (currentSum == target) { result.add(new ArrayList<>(temp)); // 重置临时变量 currentSum = 0; temp.clear(); } // 累加超过目标和，说明无法连续分割 else if (currentSum > target) { return new ArrayList<>(); } } // 最终校验分割数量是否等于k if (result.size() == k) { return result; } else { System.out.println("无法分割为" + k + "个和相等的子数组"); return new ArrayList<>(); } }

二、二维前缀和（子矩阵求和）

1. 核心原理

处理二维矩阵的子矩阵和，预处理 O (nm)，查询 O (1)

• 定义：preSum[i][j]表示从矩阵左上角 (0,0) 到 (i-1,j-1) 的矩形和
• 公式：
  • 预处理：
  • preSum[i][j] = 矩阵当前值 + 上 + 左 - 左上
  • preSum[i][j] = matrix[i-1][j-1] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1]
  • 子矩阵和（左上角 x1,y1，右下角 x2,y2）：
  • sum = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]

2、适用场景

• 多次查询矩阵中任意子矩形的和
• 矩阵区域求和、最大子矩阵和

Java示例代码

public static void main(String[] args) { // 原矩阵 int[][] matrix = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; int m = matrix.length; // 行数 int n = matrix[0].length; // 列数 // 1. 构建二维前缀和数组（(m+1)行(n+1)列，第一行第一列全0） int[][] preSum = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { // 核心公式 preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1] } } // 2. 查询子矩阵和：左上角(0,1)，右下角(2,2)（矩阵右侧两列） int x1 = 0, y1 = 1; int x2 = 2, y2 = 2; int sum = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]; System.out.println("子矩阵和：" + sum); // 输出2+3+5+6+8+9=33 }

3、典型例题

给你一个n 行 m 列的矩阵，里面只有0 和 1。

问：这个矩阵里有多少个子矩阵（小矩形）满足：1 的数量 比 0 多？

巧思1：把所有0→-1，只要一个矩形的总和 > 0，就说明 1 比 0 多

巧思2：压缩成一维：把二维问题 → 变成一维问题

• 枚举所有可能的上下两条线（上边界、下边界）
• 把两条线之间的每一列加起来
• 得到一个一维数组
• 现在问题变成：这个一维数组里，有多少段连续子数组的和 > 0（前缀和+二分查找）

public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); int n = Integer.parseInt(line[0]); int m = Integer.parseInt(line[1]); int[][] matrix = new int[n][m]; for (int i = 0; i < n; i++) { line = br.readLine().split(" "); for (int j = 0; j < m; j++) { int val = Integer.parseInt(line[j]); // 把 0 转成 -1，1 保持 1 matrix[i][j] = (val == 1) ? 1 : -1; } } long ans = 0; // 枚举上边界 for (int i = 0; i < n; i++) { //记录每一列的和 int[] colSum = new int[m]; // 枚举下边界 for (int j = i; j < n; j++) { // 更新每一列的和（从 i 到 j 行） for (int k = 0; k < m; k++) { colSum[k] += matrix[j][k]; } // 计算当前一维数组中，区间和 > 0 的子数组个数 ans += countPositiveSubarrays(colSum); } } System.out.println(ans); }

/** * 计算一维数组中，区间和 > 0 的子数组个数 * 时间复杂度 O(m log m) */ private static long countPositiveSubarrays(int[] arr) { int m = arr.length; int[] prefix = new int[m + 1]; for (int i = 0; i < m; i++) { prefix[i + 1] = prefix[i] + arr[i]; } long count = 0; // 用一个有序列表维护已经遍历过的前缀和，方便二分查找 List<Integer> sortedPrefix = new ArrayList<>(); sortedPrefix.add(prefix[0]); for (int r = 1; r <= m; r++) { int current = prefix[r]; // 找所有已有的前缀和中，小于 current 的数量 // 因为 prefix[r] - prefix[l] > 0 → prefix[l] < prefix[r] int idx = Collections.binarySearch(sortedPrefix, current); if (idx < 0) { idx = -idx - 1; } else { // 找到的是第一个等于 current 的位置，要往前找所有小于它的 while (idx > 0 && sortedPrefix.get(idx - 1).equals(current)) { idx--; } } count += idx; // 插入当前前缀和到有序列表中 sortedPrefix.add(idx, current); } return count; }

总结

1、一维前缀和：预处理 O (n)，O (1) 查区间和，公式preSum[r]-preSum[l-1]

2、二维前缀和：预处理 O (nm)，O (1) 查子矩阵和，牢记「加加减减」公式

3、进阶：前缀和 + 哈希表（和为 k 子数组）、差分 + 前缀和（区间批量修改）