C++java算法
前缀和算法：连续数组与矩阵区域和
前缀和算法解决连续数组与矩阵区域和问题。连续数组问题通过将 0 视为 -1 转化为寻找和为 0 的子数组，利用哈希表记录前缀和首次出现位置实现 O(n) 时间复杂度。矩阵区域和问题通过构建二维前缀和矩阵，在 O(1) 时间内计算任意矩形区域的元素和，整体时间复杂度为 O(mn)。提供了 C++ 与 Java 代码实现。
前缀和算法解决连续数组与矩阵区域和问题。连续数组问题通过将 0 视为 -1 转化为寻找和为 0 的子数组，利用哈希表记录前缀和首次出现位置实现 O(n) 时间复杂度。矩阵区域和问题通过构建二维前缀和矩阵，在 O(1) 时间内计算任意矩形区域的元素和，整体时间复杂度为 O(mn)。提供了 C++ 与 Java 代码实现。
题目描述：
暴力解法就是枚举所有的子数组，然后判断子数组是否满足要求。
将题目转化一下：
（1）本题让我们找出一段连续的区间，0 和 1 出现的次数相同；
（2）如果将 0 记为 -1，1 记为 1，问题就变成了找出一段区间，这段区间的和等于 0；
（3）于是，这道题的思路就和【和为 K 的子数组】类似了。
设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间中的所有元素的和。 想知道最大的以 i 结尾的和为 0 的子数组，就要找到从左往右第一个 x1 使得 [x1, i] 区间内的所有元素的和为 0。那么 [0, x1 - 1] 区间内的和是不是就是 sum[i] 了。于是这个问题就变成了——
找到在 [0, i - 1] 区间内，第一次出现 sum[i] 的位置即可。
我们不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，第一个前缀和等于 sum[i] 的位置。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边记录第一次出现该前缀和的位置。
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int,int> hash; // 创建哈希，统计前缀和出现的位置
hash[0] = -1; // 默认有一个前缀和为 0 的情况，下标为 -1
int sum = 0, ret = 0;
for(int i = 0; i < nums.size(); ++i) {
sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和
if(hash.count(sum)) { // 存在：说明此时 hash[sum] 里面存了前面那个的下标
ret = max(ret, i - hash[sum]); // 更新长度
} else {
hash[sum] = i; // 记录第一次出现的位置
}
}
return ret;
}
};
时间复杂度：O(n)，空间复杂度：O(n)。
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> hash = new HashMap<>();
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;
}
}
时间复杂度：O(n)，空间复杂度：O(n)。
题目描述：
二维前缀和的简单应用题，关键是在填写结果矩阵的时候，要找到原矩阵对应区域的【左上角】以及【右下角】的坐标。
（1）左上角坐标：x1 = i - k，y1 = j - k，但是由于会「超过矩阵」的范围，因此需要对 0 取一个 max。修正后的坐标为：x1 = max(0, i - k)，y1 = max(0, j - k)；
（2）右下角坐标：x2 = i + k，y2 = j + k，但是由于会【超过矩阵】的范围，因此需要对 m - 1，以及 n - 1 取一个 min。修正后的坐标为：x2 = min(m - 1, i + k)，y2 = min(n - 1, j + k)。
然后将求出来的坐标代入到【二维前缀和矩阵】的计算公式上即可，注意下标的映射关系。
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
// 1、预处理一个前缀和矩阵
vector<vector<int>> dp(m + 1, vector<int>(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、使用前缀和矩阵
vector<vector<int>> ret(m, vector<int>(n));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++) {
int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
int x2 = min(m - 1, i + k) + 1, y2 = min(n - , j + k) + ;
ret[i][j] = dp[x2][y2] - dp[x1 - ][y2] - dp[x2][y1 - ] + dp[x1 - ][y1 - ];
}
ret;
}
};
时间复杂度：O(mn)，空间复杂度：O(mn)。
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
// 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 - , i + k) + , y2 = Math.min(n - , j + k) + ;
ret[i][j] = dp[x2][y2] - dp[x1 - ][y2] - dp[x2][y1 - ] + dp[x1 - ][y1 - ];
}
ret;
}
}
时间复杂度：O(mn)，空间复杂度：O(mn)。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online