977.有序数组的平方

思路

最直观的解法：

暴力解题，每个数先平方，然后再快速排序，时间复杂度为 O(n + nlog n)
规律：

该数组本身是非递减顺序，在平方后其实依然有顺序，左右两边大中间小。

双指针

利用观察到的规律，可以利用双指针在数组的两头寻找最大的元素，将其放到新创建的数组中

解法：

定义两个指针，i 指向起始位置，j 指向终止位置
定义一个新数组 result，长度和 nums 一样，让 k 指向 result数组的终止位置
循环条件为 i <= j ，保证最后一个元素能够被处理移至新数组
若 nums[i] * nums[i] > nums[j] * nums[j] 那么 result[k--] = nums[i] * nums[i++]

若 nums[i] * nums[i] <= nums[j] * nums[j] 那么 result[k--] = nums[j] * nums[j--]

代码实现

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int i = 0;
        int j = nums.length - 1;
        int k = nums.length - 1;
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                result[k--] = nums[i] * nums[i];
                i++;
            } else {
                result[k--] = nums[j] * nums[j];
                j--;
            }
        }
        return result;
    }
}

209.长度最小的子数组

题目链接：209.长度最小的子数组

视频教程

文章教程

滑动窗口

滑动窗口：就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。

滑动窗口其实也可以理解为双指针的一种，只不过这种解法更像是一个窗口在移动，所以叫滑动窗口更合适一点

本题中实现滑动窗口，主要是确定如下三点：

窗口内是什么？
如何移动窗口的结束位置（快指针）？
如何移动窗口的起始位置（慢指针）？

解决思路：

窗口：满足其和 >= target 的长度最小的连续子数组
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里面的索引
窗口的起始位置如何移动：如果窗口内的值 >= target 了，窗口的起始位置就要向前移动直到窗口内的值 < target

while (sum >= target) {
    tmp = fast - slow + 1;
    min = Math.min(min, tmp);
    sum -= nums[slow++]; 
}

如何动态调节滑动窗口的起始位置是本题的精华

代码实现

时间复杂度：O(n) 2 * n

空间复杂度：O(1)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int slow = 0;
        int sum = 0;
        int tmp = 0;
        for (int fast = 0;fast < nums.length;fast++) {
            sum += nums[fast];
            while (sum >= target) {
                tmp = fast - slow + 1;
                min = Math.min(min, tmp);
                sum -= nums[slow++]; 
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

59.螺旋矩阵 Ⅱ

题目链接：59.螺旋矩阵 Ⅱ

视频链接

文章链接

思路

难点：本题不涉及什么算法，但十分考察过程，对于每一圈的边界不好处理
解决方式：坚持 循环不变量原则 ，类似 二分法 中坚持 左闭右开
过程：由外向内地循环每一圈 ，下面四个循环的边界都坚持左闭右开，这样可以避免重复填充或露填充
- 左上到右上 [不变][递增]
- 右上到右下 [递增][不变]
- 右下到左下 [不变][递减]
- 左下到左上 [递减][不变]

这里引用carl哥的图来解释说明：（图画的贼清晰）

这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。

代码实现

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int count = 1; // 递增计数
        int start = 0; // 每一圈的起始位置,每圈从(start, start)开始
        int i,j; // 方便写下面四个循环
        for (int loop = 1;loop <= n / 2;loop++) {
            // 模拟上侧从左到右
            for (j = start;j < n - loop;j++) {
                result[start][j] = count++;
            }
            // 模拟右侧从上到下
            for (i = start;i < n - loop;i++) {
                result[i][j] = count++;
            }
            // 模拟下侧从右到左
            for (;j >= loop;j--) {
                result[i][j] = count++;
            }
            // 模拟左侧从下到上
            for (;i >= loop;i--) {
                result[i][j] = count++;
            }

            start++;
        }

        // 如果n为奇数，需要单独给最中间的位置赋值
        if (n % 2 == 1) {
            result[start][start] = count;
        }
        return result;
    }
}