977.有序数组的平方
文章讲解:代码随想录-有序数组的平方
视频讲解: 双指针法经典题目
题设:给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
难点:数组有正有负,时间复杂度要求只进行一次循环。
思路:平方后的最大值会在两边,采用双指针从两边往中间逐步靠拢。
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int index = nums.length - 1;
int left = 0;
int right = nums.length - 1;
while (left <= right) {
if (nums[left] * nums[left] <= nums[right] * nums[right]) {
result[index--] = nums[right] * nums[right];
right--;
} else {
result[index--] = nums[left] * nums[left];
left++;
}
}
return result;
}
易错点:新的数组下标由大到小更新。
复杂度分析:
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。
209.长度最小的子数组
文章讲解:代码随想录-长度最小的子数组
视频讲解:拿下滑动窗口!
题设:给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度。如果不存在符合条件的子数组,返回 0
。
难点:滑动窗口的理解。
思路:一次循环要完成两个循环的功能,那么循环变量一定是指向终止位置,再用策略去更新起始位置。当窗口中的数字和大于目标数字时,再去更新起始位置。
public int minSubArrayLen(int target, int[] nums) {
int start = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
while (sum >= target) {
int length = end - start + 1;
result = Math.min(result, length);
sum -= nums[start++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
易错点:当不存在子数组时,可以通过将数组设为Integer的Max_Value,在对比过程中用Math中的min方法更新。最终条件表达式得到result的值。
复杂度分析:
- 时间复杂度:O(n)。
- 空间复杂度:O(1)。
59.螺旋矩阵II
文章讲解:代码随想录-螺旋矩阵Ⅱ
视频讲解:一入循环深似海
题设:给你一个正整数 n
,生成一个包含 1
到 n2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
难点:处理边界条件的问题,即循坏不变量。
思路:将所有遍历规则定义为左闭右开。一共要经历几次循环呢?答案是宽度/高度除以2,当n为奇数时,会留下最中心的一个点。
public int[][] generateMatrix(int n) {
int loop = 0; // 控制循环次数
int[][] res = new int[n][n];
int start = 0; // 每次循环的开始点(start, start)
int count = 1; // 定义填充数字
int i, j;
while (loop++ < n / 2) {
// 模拟上侧从左到右
for (j = start; j < n - loop; j++) {
res[start][j] = count++;
}
// 模拟右侧从上到下
for (i = start; i < n - loop; i++) {
res[i][j] = count++;
}
// 模拟下侧从右到左
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;
}
易错点:开始的x、y坐标,可用同一个变量接收。循环次数以及每次更改的边界值可用同一个变量表示。
复杂度分析:
- 时间复杂度: O(n^2),模拟遍历二维矩阵的时间。
- 空间复杂度: O(1)。