前言
聚焦算法题实战，系统讲解核心板块。优选算法部分剖析动态规划、二分法等高效策略，学会寻找'最优解'。递归与回溯掌握问题分解与状态回退，攻克组合排列难题。贪心算法理解从局部到全局的思路，解决区间调度等问题。内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
31. 连续数组
题目链接：
题目描述：
题目示例：
解法（前缀和 + 哈希表）
算法思路
稍微转换一下题目，就会变成我们熟悉的题型。
本题让我们找出一段连续的区间，其中 0 和 1 出现的次数相同。如果将 0 记为 -1，1 记为 1，问题就变成了找出一段区间，这段区间的和等于 0。
找到在 [0, i-1] 区间内，第一次出现 sum[i] 的位置即可。
于是，就和之前做过的那个和为 k 的子数组的题思路类似了。
设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。
想知道最大的【以 i 结尾的和为 0 的子数组】，就要找到从左往右第一个 x1 使得 [x1, i] 区间内所有元素的和为 0。那么 [0, x1-1] 区间内的和是不是就是 sum[i] 了。于是问题就变成：
我们还是不用真的初始化一个前缀和数组，因为我们只关心 i 位置之前，第一个前缀和等于 sum[i] 的位置，因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边记录第一次出现该前缀和的位置。
C++ 算法代码
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> hash;
hash[0] = -1; // 默认前缀和为 0 的情况有一个，但这里注意我们的后面一个 int 是存下标的
int sum = 0, ret = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和，并且数组中为 0 的改成 -1
if (hash.count(sum))
ret = max(ret, i - hash[sum]);
else
hash[sum] = i;
}
return ret;
}
};
算法总结 && 笔记展示
32. 矩阵区域和
题目链接：
题目描述：
题目示例：
解法
算法思路
二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对于区域的【左上角】以及【右下角】的坐标（大家可以画图，我后面的笔记里会有）。
- 左上角坐标：
x1 = i - k，y1 = j - k，但是由于会【超过矩阵】的范围，因此需要对0取一个max。因此修正后的坐标为：x1 = max(0, i-k)，y1 = max(0, j-k)； - 右下角坐标：
x2 = i + k，y2 = j + k，但是由于会【超过矩阵】的范围，因此需要对m - 1，以及n-1取一个min。因此修正后的坐标为：x2 = min(m-1, i+k)，y2 = min(n-1, j+k)。
然后将求出来的坐标代入到【二维前缀和矩阵】的计算公式上即可~（但是要注意下标的映射关系，这个这里就不仔细讲了，下面也会在笔记中展示出来）
C++ 算法代码
class Solution {
public:
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
vector<vector<int>> answer(m, vector<int>(n));
// 预处理出来一个 dp 数组
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];
// 使用 dp 数组
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 - 1, j + k) + 1;
answer[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}
return answer;
}
};
算法总结 && 笔记展示
