977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
Tips
递增数据的平方，每次都能找到一个最大值，放入结果最右侧
思路
- 递增数组，平方后最大值一定在最左侧或者最右侧，可想到–双指针
- 左右指针向中间靠拢，每次可以得到一个最大值，以此类推，放入结果集中
- 临界条件需要左右指针相等，不会漏掉最后一个数
复杂度
- 时间 O(n)
- 空间 O(n)
class Solution {
public int[] sortedSquares(int[] nums) {
int[] rt = new int[nums.length];
int l = 0 ,r = nums.length-1,pos = r ;
while(l<=r){
int lv = nums[l] * nums[l] ;
int rv = nums[r] * nums[r];
if(lv < rv){
rt[pos--] = rv ;
--r;
}else{
rt[pos--] = lv ;
++l;
}
}
return rt;
}
}
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思考
- 最小数据需要逐个判断子数据的长度，可想到滑动窗口
- 动态子数组的最小长度，可想到快慢指针，快指针得到满足条件的子数组时，移动慢指针
- 慢指针的移动需要借助循环来实现，即需要两层循环
复杂度
暴力解法
- 固定一个数，往后循环，找到大于等于目标值结束
- 时间复杂度O(n*n)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ml = Integer.MAX_VALUE,sum = 0 ;
for (int i = 0; i < nums.length; i++) {
sum = nums[i];
if(sum>=target) return 1 ;
for (int j = i+1; j < nums.length; j++) {
sum += nums[j];
if(sum >= target){
ml = Math.min(ml,j-i +1);
break;
}
}
}
return ml != Integer.MAX_VALUE ? ml : 0 ;
}
}
快慢指针+滑动窗口
- 时间 O(2n)==>O(n)
- 空间 O(1)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int l = 0 ,r = 0 ,sum = 0 , ml = Integer.MAX_VALUE;
while(r < nums.length){
sum += nums[r];
while(sum >= target){
ml = Math.min(ml, r-l+1);
sum -= nums[l++];
}
++r;
}
return ml != Integer.MAX_VALUE ? ml : 0 ;
}
}
59.螺旋矩阵II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix
思考
- 按顺时针旋转，旋转一周可得到四条边，分别为上、右、下、左
- 每条边的下标的临界值为0或者n-1，循环为左右闭区间，故走完一条边就要把这条边消掉，（起名为剥洋葱）
- 走完一周，相当消掉一周的边，是不是很像剥洋葱，一层一层的剥开…
class Solution {
public int[][] generateMatrix(int n) {
//四条边left rigth top bottom 根据旋转方向得到每条边的临界值，类似洋葱剥皮
//每个方向的临界值
int l = 0 , t = 0 ,r = n-1 ,b = n-1,num = 1 ;
int[][] res = new int[n][n];
while(num <= n * n){
//上层 t不变 l->r
for(int i = l ; i<=r ; i++ ){
res[t][i] = num++;
}
t++ ;
//右侧 r不变 t->b
for(int i = t ; i<=b ; i++ ){
res[i][r] = num++ ;
}
r--;
//底部 b不变 r->l
for(int i = r ; i>=l ;i--){
res[b][i] = num++;
}
b--;
//左侧 r不变 b->t
for(int i = b ;i>=t ; i--){
res[i][l] = num++;
}
l++;
}
return res ;
}
}