c++ 算法学习第二天|数组

数组专题学习安排与要点总结

一、209. 长度最小的子数组（滑动窗口）

🎯学习重点

• 第一次系统理解「滑动窗口」思想**
• 理解「窗口不是固定大小，而是动态伸缩」
• 明确两个指针的含义：
  • left：窗口起点
  • right：窗口终点
• 核心逻辑：
  • 先扩张窗口（right++）
  • 当条件满足时，尝试收缩窗口（left++）
• 明白：
  • 为什么是 while (sum >= target)
  • 为什么可以在 O(n) 内完成

⚠️ 学习建议

• 文字讲解偏抽象，建议直接看洛谷题解的动图 先理解「窗口在动」

我一开始想成先把数组换成升序数组，然后再从后面累加到大于targe就好，
但忽略了题目中是要求连续数组，所以不能用这种方法

• 这时候用滑动窗口就可以完美解决 自己解的代码如下

classSolution{public:intminSubArrayLen(int target, vector<int>& nums){int end =0, ans =1e6;int sum =0;for(int start =0; start < nums.size();){while(sum < target && end < nums.size()){ sum += nums[end]; end++;}if(sum >= target){ ans =min(ans,end-start); sum -= nums[start]; start++;}elsebreak;}if(ans ==1e6)return0;elsereturn ans;}};

• 官方题解 我觉得更好

classSolution{public:intminSubArrayLen(int target, vector<int>& nums){int n = nums.size();if(n ==0)return0;int ans = INT_MAX;int start =0, end =0;int sum =0;while(end < n){ sum += nums[end];while(sum >= target){ ans =min(ans, end - start +1); sum -= nums[start]; start++;} end++;}return ans == INT_MAX ?0: ans;}};

二、59. 螺旋矩阵 II（模拟 + 区间定义）

学习重点

• 本质是「模拟」问题，不是数学题
• 核心在于：
  • 转圈的顺序
  • 每一圈的边界定义
• 学会使用：
  • 左闭右开 / 左闭右闭 即区间思想
• 理解为什么：
  • 每一圈都要缩小边界
  • 奇数阶矩阵最后有一个中心点

⚠️ 学习建议

• 写代码前先在电脑画图画 3×3、4×4
• 搞清楚「一圈」是如何走完的
• 搞清楚输入n会有几圈，
• 再敲代码

n是偶数 有n/2圈 比如n=4 有两圈
n是奇数 有n/2圈 圈完还剩中间的一个数

int start =0, x, y;int offset =1, count =1;int loop = n /2; vector<vector<int>>num(n,vector<int>(n,0));while(loop--){for(y = start; y < n - offset; y++){ num[start][y]= count++;}for(x = start; x < n - offset; x++){ num[x][y]= count++;}for(; y > start; y--){ num[x][y]= count++;}for(; x > start; x--){ num[x][y]= count++;} start++; offset++;}if(n %2==1){int mid = n /2; num[mid][mid]= n * n;}

*另外要复习的点：
vector二维数组
vector<vector> arr(n,vector(m,0);

三、区间和（前缀和思想）

学习重点

• 前缀和是一种非常重要且高频的思想
• 核心公式：sum[l…r] = p[ right ] - p[left - 1]
  • 前缀和解决的问题本质：
• 把「多次重复计算」变成「一次预处理」
• 优势：
• 从 O(n) 查询 → O(1) 查询
• 适用场景：
• 多次区间求和
• 后续会大量用于 DP、哈希、二维数组

本来用一个数组存入，然后for循环累加到sum就好
但是存在一个严重的问题，如果要求计算很多次，即while很多次，时间超时

#include<bits/stdc++.h>usingnamespace std;intmain(){int n,first=0; cin>>n; vector<int>num(n); vector<int>p(n+1,0);for(int i=0; i<n; i++){ cin>>num[i]; first += num[i]; p[i]= first;}int start,end;while(cin>>start>>end){int sum=0;if(start ==0) sum= p[end];else{ sum = p[end]- p[start-1];} cout<<sum<<endl;}}

四、开发商购买土地（前缀和综合应用）

🎯 学习重点

• 前缀和的实际应用题
• 核心思想：
• 横着切 or 竖着切
• 找到两部分和最接近的方案
• 关键在于：
• 如何快速算「一整块区域的和」
• 训练点：
• 把抽象问题转化为数组/前缀和模型

#include<bits/stdc++.h>usingnamespace std;intmain(){int n,m; cin>>n>>m; vector<vector<int>>num(n,vector<int>(m,0));int sum=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){ cin>>num[i][j]; sum+=num[i][j];}} vector<int>heng(n);for(int i=0;i<n;i++){for(int j=0;j<m;j++){ heng[i]+= num[i][j];}} vector<int>shu(m);for(int j=0;j<m;j++){for(int i=0;i<n;i++){ shu[j]+= num[i][j];}}int result = INT_MAX;int hengcut;for(int i=0;i<n;i++){ hengcut += heng[i]; result =min(result,abs(sum-hengcut-hengcut));}int shucut =0;for(int j=0;j<m;j++){ shucut += shu[j]; result =min(result,abs(sum-shucut-shucut));} cout<<result<<endl;return0;}

五、数组专题总结（非常重要）

🎯 这两天

• 建立数组题的整体认知框架：
• 二分查找
• 双指针
• 滑动窗口
• 前缀和
• 模拟
• 明确：
• 不同题型的「固定解题套路」
• 什么时候该想到哪种方法
• 建议：
• 自己写一份 “数组题常用模板”
• 以后刷题直接套思想，而不是现想