双指针法
滑动窗口
模拟过程
977.有序数组的平方
977. 有序数组的平方 - 力扣（LeetCode）
两个解题思路
- 暴力解法
- 双指针法
暴力解法
暴力解法的思路就是把每个数组平方以后，再进行排序。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i = 0;i<nums.size();i++)//for循环遍历数组中的所有元素
{
nums[i]*=nums[i];//对元素进行平方操作
}
sort(nums.begin(),nums.end());//将平方后的元素进行排序
return nums;//返回平方操作后的新数组
}
};
双指针法
解题思路就是创建两个指针，一个指针i从起始位置向终止移动，一个j由终止位置向起始位置移动。
在对一个非递减的数组进行平方排序后，最大值不是在最左边就是在最右边，所以只要对两端元素的平方进行比较以后，就能得到新数组的最大值。
定义一个新数组result，定义一个指向数组尾端的下标k，更新的元素从后向前添加k--。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size()-1;//新数组指向终止位置
vector<int> result(nums.size(),0);//新数组
for(int i=0,j=nums.size()-1;i<=j;)//注意for循环中的条件表达式
{
if(nums[i]*nums[i]<nums[j]*nums[j])
{
result[k--]=nums[j]*nums[j];
j--;
}
else
{
result[k--]=nums[i]*nums[i];
i++;
}
}
return result;
}
};
209.长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）
两个解题思路
- 暴力解法
- 滑动窗口
暴力解法
使用两个for循环，一个为数组的起始位置，一个为数组的终止位置，用来寻找符合条件的子数组。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;//在32位有符号整数中，INT32_MAX是最高位
int sum = 0;//表示子数组的和
int longth = 0;//子数组的长度
for(int i = 0;i<nums.size();i++)
{
sum=0;
for(int j = i;j<nums.size();j++)//从第i个位置开始，一个元素一个元素进行对比
{
sum+=nums[j];
if(sum>=target)//如果找到符合条件的最小数组
{
longth=j-i+1;//得到数组长度
result=result<longth?result:longth;//将数组长度赋给结果
break;
}
}
}
return result==INT32_MAX?0:result;//如果这个最小数组不存在，输出0
}
};
时间复杂度O（n^2）
空间复杂度O（1）
滑动窗口
也可以理解为双指针的一种，通过不断地改变两个指针的位置，从而动态的找到符合目标条件的最小数组。
- 指针i不动，指针j通过不断地后移找到目标数组，若数组和超过目标值就开始移动i起始指针，找到最小数组。
- 两个指针的定义是i为最小数组的起始位置，j为最小数组的终止位置。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;//定义一个最大值，其他数值不会超过它
int sum = 0;//最小数组的和
int longth = 0;//最小数组的长度
int i = 0;//最小数组起始位置
for(int j = 0;j<nums.size();j++)//定义最小数组的终止位置
{
sum += nums[j];
while(sum>=target)
{
longth = j-i+1;//计算数组长度
result=result<longth?result:longth;
sum-=nums[i++];//滑动窗口，通过不断改变起始位置找最小数组
}
}
return result==INT32_MAX?0:result;
}
};
时间复杂度O(n)
空间复杂度O（1）
59.螺旋矩阵||
解题思路
这是一个模拟过程的题目，在做螺旋矩阵式的一个难点就是对边界的处理。
- loop=n/2，表示了矩阵转了几圈，在每一圈的转弯处处理的边界条件都不一样，所以要想办法让处理边界条件的方法一致。
- 选择左闭右开的方式，即每一行的第一个边界点，其下一个边界点交给下一行。
- 通过对矩阵下标的观察，模拟出上下左右四个方向矩阵赋值的规律
- 若n为奇数，单独留出中间位置为其赋值。
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector <int>> res(n,vector(n,0));
int x=0,y=0;//定义螺旋矩阵的起始位置
int mid=n/2;//如果n为奇数，mid为中间位置赋值
int count = 1;//给空格赋值
int offset=1;//为螺旋矩阵边界进行限制
int loop=n/2;
while(loop--)
{
int i=x;
int j=y;
for(j=y;j<n-offset;j++)
{
res[i][j]=count++;//模拟从左到右
}
for(i=x;i<n-offset;i++)
{
res[i][j]=count++;//模拟从上到下
}
for(;j>y;j--)
{
res[i][j]=count++;//模拟从右到左
}
for(;i>x;i--)
{
res[i][j]=count++;//模拟从下到上
}
x++;
y++;
offset+=1;
}
if(n%2)
{
res[mid][mid]=count;
}
return res;
}
};
