《算法闯关指南：优选算法--前缀和》--31.连续数组，32.矩阵区域和

🔥草莓熊Lotso：个人主页
❄️个人专栏: 《C++知识分享》《Linux 入门到实践：零基础也能懂》
✨生活是默默的坚持，毅力是永久的享受！

🎬 博主简介：

文章目录

• 前言：
• 31. 连续数组
  • 解法（前缀和+哈希表）：
    • 算法思路：
  • C++算法代码：
  • 算法总结&&笔记展示：
• 32. 矩阵区域和
  • 解法：
    • 算法思路：
  • C++算法代码：
  • 算法总结&&笔记展示：
• 结尾：

前言：

聚焦算法题实战，系统讲解三大核心板块：优选算法：剖析动态规划、二分法等高效策略，学会寻找“最优解”。 递归与回溯：掌握问题分解与状态回退，攻克组合、排列等难题。 贪心算法：理解“局部最优”到“全局最优”的思路，解决区间调度等问题 内容以题带点，讲解思路与代码实现，帮助大家快速提升代码能力。

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.矩阵区域和通过二维前缀和快速计算矩阵区域和，注意处理边界条件。代码实现清晰，附手写笔记图解关键思路，适合算法学习者提升实战能力。

✨把这些内容吃透超牛的！放松下吧✨ʕ˘ᴥ˘ʔづきらど