209.长度最小的子数组
题目链接：209.长度最小的子数组
文档讲解：代码随想录
状态：暴力解决，学会滑动窗口法
思路
本题关键点在于最小子串、正整数元素
初始的想法：暴力解法，第一层for循环选择字串起点，第二层遍历寻找终点，不断比较更新得到结果。
滑动窗口法：维护两个指针，根据单调性，想找到解必须尾指针向右移动（sum增加），想确定这个解是不是这一大部分的最优解，一定是头指针向右移动（都是整数，sum想减小必须向右），遍历两次即可得解。
双指针移动图解：
关键代码图解：
题解
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums)
{//暴力解法
// int result = INT32_MAX;
// for(int i = 0;i<nums.size();i++)
// {
// int sum = 0,temp = 0;
// for(int j = i;j<nums.size();j++)
// {
// sum += nums[j];
// temp++;
// if(sum >= target)result = temp<result?temp:result;
// }
// }
// if(result == INT32_MAX)return 0;
// else return result;
// }
//双指针，利用正数单调性
int result = INT32_MAX, sum = 0, temp = 0;
for(int j = 0,i = 0;j<nums.size();j++)
{
sum += nums[j];
while(sum>=target)
{
temp = j-i+1;
result = temp<result?temp:result;
sum -= nums[i++];
}
}
if(result == INT32_MAX)return 0;
else return result;
}
};
59.螺旋矩阵II
思路
一看题目就知道围绕二维数组做文章，首先知道vector创建二维数组的方式vector<vector<int>> vec(3, vector<int>(4));->创建3×4数组
此题没有什么经典算法，但是学习题解大有感悟，如下图所示，数组行列之间没有规律，仅能螺旋赋值,有→、↓、←、↑四种方式。
代码随想录中的题解太过于啰嗦，转几圈，每圈位置如何递减，奇偶区别等，有没有一劳永逸的方法？有！四种方向用数组表示DIRS[4][2]搭配i+DIRS[di][0]与j+DIRS[di][1]就实现了全向移动。之前最麻烦的循环条件现在转变为了边界处理，岂不简单？x<0 || x>=n || y<0 || y>=n || ans[x][y]不越界，有位置就能为所欲为。
题解
class Solution {
public:
vector<vector<int>> generateMatrix(int n)
{
int DIRS[4][2] = {[0,1],[1,0],[0,-1],[-1,0]};//网站格式原因，将{}写为[]
vector ans(n,vector<int>(n));
int i = 0,j = 0,di = 0;
for(int val = 1;val<=n*n;val++)
{//赋值
ans[i][j] = val;
//判断下一位置
int x = i+DIRS[di][0];
int y = j+DIRS[di][1];
if(x<0 || x>=n || y<0 || y>=n || ans[x][y]) di = (di+1)%4;
//移动
i = i+DIRS[di][0];
j = j+DIRS[di][1];
}
return ans;
}
};
58.区间和
思路
ACM模式不用说了，正是拿手的地方
前缀和思想主要应用于区间和问题，正常暴力解法极其简单，但是n数组m次搜索，复杂度O(mn)稍大些（话说这么简单就是不太对头）。优化思路总结贯通为前缀和（复杂度O(n)），如下图所示，想统计vec数组上2到5下标之间的累加和，那是不是就用 p[5] - p[1] 就可以了。
可谓一劳永逸
题解
#include <iostream>
#include <vector>
using namespace std;
int main()
{
//暴力解法
// vector<int> vec;
// int n = 0;
// cin>>n;
// while(n--)
// {
// int x = 0;
// cin>>x;
// vec.push_back(x);
// }
// int start = 0, end = 0;
// while(cin>>start>>end)
// {
// int sum = 0;
// for(int i = start;i<=end;i++)
// {
// sum += vec[i];
// }
// cout<<sum<<endl;
// }
// return 0;
//前缀和
vector<int> vec;
int n = 0;
cin>>n;
for(int i = 0;i<n;i++)cin>>vec[i];
int start = 0, end = 0;
while(cin>>start>>end)
{
int sum = 0;
for(int i = start;i<=end;i++)
{
sum += vec[i];
}
cout<<sum<<endl;
}
return 0;
}
44.开发商购买土地
题目链接：44.开发商购买土地
文档讲解：代码随想录
状态：不会做，但是理清题解清楚了
思路
不考虑暴力解法
优化版本把这个题目看作模拟，关键点是整体sum与部分做差比较
本题的多维前缀和其实是针对于求解前两行、前三行的和（可看作区间和），但是本题本质不用多次求解，故前缀和没有起到太大方便作用。
题解
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main()
{ // 模拟解法
// int n = 0, m = 0, sum = 0, result = INT_MAX;
// cin>>n>>m;
// vector<vector<int>> vec(n,vector<int>(m,0));
// for(int i = 0;i<n;i++)
// {
// for(int j = 0;j<m;j++)
// {
// cin>>vec[i][j];
// sum += vec[i][j];
// }
// }
// //行确定
// int temp_sum = 0;
// for(int i = 0;i<n;i++)
// {
// for(int j = 0;j<m;j++)
// {
// temp_sum += vec[i][j];
// if(j == m-1)result = abs(sum-temp_sum-temp_sum)<result?abs(sum-temp_sum-temp_sum):result;//用j == m-1作为行分割
// }
// }
// //列确定
// temp_sum = 0;
// for(int j = 0;j<m;j++)
// {
// for(int i = 0;i<n;i++)
// {
// temp_sum += vec[i][j];
// if(i == n-1)result = abs(sum-temp_sum-temp_sum)<result?abs(sum-temp_sum-temp_sum):result;//用i == n-1作为列分割
// }
// }
// cout<<result<<endl;
//前缀和法
int n = 0, m = 0, sum = 0, result = INT_MAX;
cin>>n>>m;
vector<vector<int>> vec(n,vector<int>(m,0));
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cin>>vec[i][j];
sum += vec[i][j];
}
}
vector<int> vex(n,0);
for(int i = 0;i<n;i++)
{
int temp_sum = 0;
for(int j = 0;j<m;j++)
{
temp_sum += vec[i][j];
}
if(i == 0)vex[i] = temp_sum;
else vex[i] = temp_sum + vex[i-1];
}
vector<int> vey(m,0);
for(int j = 0;j<m;j++)
{
int temp_sum = 0;
for(int i = 0;i<n;i++)
{
temp_sum += vec[i][j];
}
if(j == 0)vey[j] = temp_sum;
else vey[j] = temp_sum += vey[j-1];
}
for(int i = 0;i<n;i++) result = min(abs(sum-vex[i]-vex[i]), result);
for(int j = 0;j<m;j++) result = min(result, abs(sum-vey[j]-vey[j]));
cout<<result<<endl;
return 0;
}
数组总结
做了一些数组的题目，我的感受是数组的关键点在于玩好下表，不管是二分、删除（覆盖）、双指针、螺旋，难点都在于如何管理好代表下标的指针，以及边界条件的判断。
还要重点关注数组中元素的性质，正or负、有序or无序等等，灵活选择头/尾或者中间下手处理数组，充分利用好题目条件。