Leetcode 977-有序数组的平方
题目描述：
https://leetcode.cn/problems/squares-of-a-sorted-array/description/
解题思路
暴力算法
在看到这道题后，最容易想到的解法是先对数组中的元素平方，然后再进行排序，代码如下：
class Solution {public:
vector sortedSquares(vector& nums) { for (int i = 0; i < nums.size(); i++) { nums[i] = nums[i] * nums[i];
}
//使用vector的sort函数对其进行快速排序,需要声明#include
sort(nums.begin(),nums.end());
return nums;
}
};
暴力解法的时间复杂度是 O ( n + n l o g ( n ) ) O(n+nlog(n)) O(n+nlog(n))，我们可以通过双指针来优化这个算法
双指针法
通过观察我们可以发现，平方后的数组最大值一定出现在两端，平方后的数字呈现出两边大中间小的状态，因此，我们可以从两端分别设置两个指针，每一次循环比较两个指针的元素平方的大小，由此得到新数组的排序。
代码如下：
class Solution {public:
vector sortedSquares(vector& nums) { int size = nums.size() - 1;//nums元素的个数
vectorresult(size+1); //设置一个存放结果的新vector
for (int i = 0, j = nums.size()-1; i <= j;) {//定义i和j两个指针，i从vector左侧出发，j从右侧出发，循环截止的条件是两个指针相遇
if (nums[i] * nums[i] < nums[j] * nums[j]) { result[size] = nums[j] * nums[j];
size--;
j--;
}
else { result[size] = nums[i] * nums[i];
size--;
i++;
}
}
return result;
}
};
此时，通过双指针的引入，我们成功将这道题的复杂度优化为 O ( n ) O(n) O(n)
Leetcode 209-长度最小的子数组
题目描述：
https://leetcode.cn/problems/minimum-size-subarray-sum/
解题思路
暴力解法：
先给出这道题的暴力解法：
class Solution {public:
int minSubArrayLen(int target, vector& nums) { int length = pow(10, 5);
for (int i = 0; i < nums.size(); i++) { int sum = 0, temp = 0, j = i;
while ((sum < target) && (j < nums.size())) { sum += nums[j];
temp++;
j++;
}
if (sum >= target) { length = min(length, temp);
}
}
return length == pow(10, 5) ? 0: length;
}
};
滑动窗口：
在暴力解法的基础上，我们可以通过滑动窗口（也可以理解为双指针）的方式优化代码，将暴力解法中的两层循环变为一层，首先我们要考虑指针的设置是从作为数组的起始点还是结束点，不难想出，如果指针作为起始点的话，后续还需要遍历整个数组寻找符合条件的子数组，这与暴力解法的思路无异，因此我们可以考虑将指针设置为数组的右侧点解决这道问题。
class Solution {public:
int minSubArrayLen(int target, vector& nums) { int i = 0;
int length = INT32_MAX;
int sum = 0;
int temp = 0;//当前子数组的大小
for (int j = 0; j < nums.size(); j++) { sum += nums[j];
while (sum >= target) {//如果子数组之和大于等于目标值，则返回其长度；注意这里是循环而不是判断，因为sum减去nums[i]后的子数组可能仍符合条件，需要通过循环不断判断
temp = j - i + 1;
length = length < temp ? length : temp;
sum -= nums[i];
i++;
}
}
return length == INT32_MAX ? 0 : length;
}
};
相似题目：
Leetcode904-水果成篮：
https://leetcode.cn/problems/fruit-into-baskets/
Leetcode76-最小覆盖子串：
https://leetcode.cn/problems/minimum-window-substring/description/
Leetcode 59-螺旋矩阵 II
题目描述：
https://leetcode.cn/problems/spiral-matrix-ii/description/
解题思路
在遍历每次循环时，需要注意将每条边处理的边界设置相同，这样便于处理边界条件。在本题的代码实现上，对于每条边选择左闭右开的区间，这样可以保证每次循环中四条边的边界条件相同。
class Solution {public:
vector> generateMatrix(int n) { vector> matrix(n, vector(n, 0));//用vector初始化一个(n,n)的二维数组
int loop = n / 2;螺旋矩阵旋转的次数为n/2，对于n为奇数时，最后会剩下n^2的数值，需要在最后进行添加
int i, j;
int startx = 0, starty = 0;//定义每次循环的起始点的位置，易知每次循环后新的起始点是上一次起始点x和y分别+1
int offset = 1;
int content = 1;
while (loop > 0) { i = startx, j = starty;//每次循环开始时初始化i和j
for (j; j < n - offset;j++) { matrix[i][j] = content;
content++;
}
for (i; i < n - offset; i++) { matrix[i][j] = content;
content++;
}
for (j; j > starty; j--) { matrix[i][j] = content;
content++;
}
for (i; i > startx; i--) { matrix[i][j] = content;
content++;
}
loop--;
startx++, starty++;
offset++;
}
if (n % 2 == 1) { matrix[startx][starty] = content;
}
return matrix;
}
};
相似题目：
Leetcode54-螺旋矩阵：
https://leetcode.cn/problems/spiral-matrix/description/
Leetcode146-螺旋遍历二维数组：
https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/