文章目录
- 长度最小的子数组
- 螺旋矩阵II
- 数组总结
长度最小的子数组
题目链接：209. 长度最小的子数组
滑动窗口法的解题思路：
- 首先初始化双指针，都指向数组头部
- end指针依次向后滑，每向后滑一项就加一项，直到满足要求达到的大小为止
- end指针不动，head指针向后滑，每向后滑一项就减一项，这也就是在尝试缩小窗口大小，直到不满足大小为止
- 更新窗口的最小长度
- 如此循环往复直到end指针未知异常（超出数组范围）
- 最后返回窗口的最小长度即可
- 这里有一个容易遗漏的情况就是，数组的所有元素加起来都没达到要求，这个时候就要返回0
class Solution {public int minSubArrayLen(int target, int[] nums) {int head = 0;int total = 0;int minLength = Integer.MAX_VALUE;for(int end = 0; end < nums.length; end++) {total += nums[end];if(total < target) {if (head == 0 && end == nums.length - 1) return 0;continue;}while (total - nums[head] >= target) total -= nums[head++];int currentLength = end - head + 1;if(currentLength < minLength) minLength = currentLength;}return minLength;}
}
螺旋矩阵II
题目链接： 59. 螺旋矩阵 II
本题首先观察题目特点：
- 填充路线都是在一个方向上进行到底才转向
- 往哪转？可以从向量的角度来看，如下图
- 这张图中通过单位向量的方式，描述了每次转向的方向（同时也代表了每次移动的坐标变化量）
- 我们可以总结出每次转向都是（x，y） --> （y，-x）
接下来开始编码：
class Solution {public int[][] generateMatrix(int n) {int[][] result = new int[n][n];int x = 0;int y = 0;int direct_x = 0;int direct_y = 1;for (int i = 1; i <= n * n; i++) {result[x][y] = i;int try_x = x + direct_x;int try_y = y + direct_y ;if (try_x > n - 1 || try_y > n - 1 || try_x < 0 || try_y < 0 || result[try_x][try_y] != 0) {int temp = direct_y;direct_y = -direct_x;direct_x = temp;}x += direct_x;y += direct_y;}return result;}
}
转向的边界判断可以使用取模的方式简化
数组总结
数组的相关算法题，比较常用的就是四种方法：
- 二分法
- 双指针法： 两个指针的动向比较灵活，但不能违背指针的前后次序
- 滑动窗口法： 可以理解为双指针法的变种，两个指针具有单调性，均往一个方向走，区间的变化是一种收缩，满足元素剔除的思想
- 行为模拟： 一定要弄清楚题目的特点，涉及到多维数组，可以从数学的角度来看待，通过建系的方法，把行为转化为坐标的变化从而进行解题
