《算法闯关指南：优选算法--前缀和》--31.连续数组，32.矩阵区域和
🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！
🎬 博主简介：
文章目录
前言：
聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。
31. 连续数组
题目链接：
525. 连续数组 - 力扣（LeetCode）
题目描述：
题目示例：
解法（前缀和+哈希表）：
算法思路：
稍微转换一下题目，就会变成我们熟悉的题：
- 本题让我们找出一段连续的区间，
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++算法代码：
classSolution{public:intfindMaxLength(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. 矩阵区域和
题目链接：
1314. 矩阵区域和 - 力扣（LeetCode）
题目描述：
题目示例：
解法：
算法思路：
二维前缀和的简单应用题，关键就是我们在填写结果矩阵的时候，要找到原矩阵对于区域的【左上角】以及【右下角】的坐标（大家可以画图，我后面的笔记里会有）
- 左上角坐标：
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++算法代码：
classSolution{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;}};算法总结&&笔记展示：
笔记字有点丑，大家见谅：
结尾：
🍓 我是草莓熊 Lotso！若这篇技术干货帮你打通了学习中的卡点： 👀 【关注】跟我一起深耕技术领域，从基础到进阶，见证每一次成长 ❤️ 【点赞】让优质内容被更多人看见，让知识传递更有力量 ⭐ 【收藏】把核心知识点、实战技巧存好，需要时直接查、随时用 💬 【评论】分享你的经验或疑问（比如曾踩过的技术坑？），一起交流避坑 🗳️ 【投票】用你的选择助力社区内容方向，告诉大家哪个技术点最该重点拆解 技术之路难免有困惑，但同行的人会让前进更有方向～愿我们都能在自己专注的领域里，一步步靠近心中的技术目标！ 结语：本文聚焦算法实战，通过两道力扣题目详解前缀和与哈希表的应用。525.连续数组将0/1转换后用前缀和+哈希表寻找和为0的最长子数组；1314.矩阵区域和通过二维前缀和快速计算矩阵区域和，注意处理边界条件。代码实现清晰，附手写笔记图解关键思路，适合算法学习者提升实战能力。
✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど
