DAY2
944 有序数组的平方
刚开始自己做就是无脑ac的，sort：
但是时间复杂度有问题， 是O(nlogn)的时间复杂度
class Solution {
public int[] sortedSquares(int[] nums) {
for(int i=0;i<nums.length;i++){
nums[i] =nums[i]*nums[i];
}
Arrays.sort(nums);
return nums;
}
}
提升：用双指针的思想：时间复杂度为O(n)
使用双指针的思想解决本题的思路：
以数组 为例：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
因为输入的数组是递增的，因此，平方后的最大值，只有可能在最左侧和最右端出现：
定义：
1 定义一个新数组result，和nums数组一样的大小
2 定义两个指针： left 指向起始位置，right指向终止位置。
3 定义一个index指针：让index指向result数组终止位置，用index来向新数组存放数据： 依次从新数组的后面向前存数据，存的数据是旧数组中比较得来的较大的值；这样就可以保证新数组中依次存放的是(旧数组中数据平方后的增序排序了)。
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];//新数组；
int left =0;
int right=nums.length-1;
int index = nums.length-1;
while(left<=right){
if(nums[left]*nums[left]<=nums[right]*nums[right]){
res[index] = nums[right]*nums[right];
index--;
right--;
}else{
res[index] = nums[left]*nums[left];
index--;
left++;
}
}
return res;
}
}
注意点：
写代码的时候要注意while(left<=right)这个条件，只要left<=right的时候，我们就要一直循环比较下去：因为如果是left==right的时候就退出来不进行while循环了，就会将这个元素落下来，但是实际上我们是仍然要更新这个值放在新数组中的，要保证数组的完整性，因此不可以用left<=right这个条件；还有一个if(...<=....)等于号的问题，其实写不写都行，因为else后面其实就包含了等于的情况，更新的话也是更新哪个都可以的；
209 长度最小的子数组
题目描述:
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
思路：
用双指针+滑动窗口的思想
滑动窗口：
其实就是满足我们条件的所有子数组连续的子数组
双指针 ：
// 定义左边界：当找到一个的时候，就要缩小滑动窗口
// 定义右边界：主要就是负责寻找子数组的
滑动窗口的思想:
窗口就是 满足其和 ≥ target 的长度最小的连续子数组。
窗口的起始位置的移动：一旦当前窗口的值大于target了（count >= target），就要缩小滑动窗口，也就是左指针++。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 滑动窗口：其实就是满足我们条件的所有子数组连续的子数组
// 定义左边界:当找到一个的时候 就要缩小滑动窗口
// 定义右边界:主要就是负责寻找子数组的
int left=0;
// int right;
//定义数组长度 以及更新最小子数组的长度！
int length=0;
int minLength=0;
//定义累计计数
int count=0;
// 用右指针遍历数组
for(int right=0;right<nums.length;right++){
count = count + nums[right];// 根据题意进行数据的累加
// 注意这里不能用if 要用while 因为要在数组中不断的寻找最小
// 一旦大于target就要缩小窗口 即移动左指针
while(count >= target){
length = right - left + 1;
// 注意一定有这个 因为如果第一个数就比target大呢 这时候minLength为0
// 当前的长度比最小的长度还小 更新最小长度
if(length < minLength ||minLength ==0 ){
minLength = length;
}
// 缩小滑动窗口: count缩小 left右移动
count = count - nums[left];
left++;
}
}
return minLength;
}
}
59 螺旋矩阵
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
处理的边界条件是不同的
坚持一个规则来处理每一条边
用左必右开的左文章来源：https://www.toymoban.com/news/detail-402970.html
代码：文章来源地址https://www.toymoban.com/news/detail-402970.html
class Solution {
public int[][] generateMatrix(int n) {
// 模拟题.
int loop = 0; // 控制循环次数
int[][] res = new int[n][n];//遍历的结果数组
int start = 0; // 每次循环的开始点(start, start)
int count = 1; // 定义填充数字 从1 开始
int i, j; // j 是遍历行的 i是遍历列的
while (loop++ < n / 2) { // 判断边界后，loop从1开始
// 模拟上侧从左到右
for (j = start; j < n - loop; j++) {
res[start][j] = count++;
}
// 模拟右侧从上到下
for (i = start; i < n - loop; i++) {
res[i][j] = count++;
}
// 模拟下侧从右到左 j不用初始化了
for (; j >= loop; j--) {
res[i][j] = count++;
}
// 模拟左侧从下到上
for (; i >= loop; i--) {
res[i][j] = count++;
}
start++;
}
if (n % 2 == 1) {
res[start][start] = count;
}
return res;
}
}
到了这里，关于刷题（双指针思想/滑动窗口思想/l螺旋矩阵）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
