[数据结构与算法]代码随想录算法训练营第二天 | 977.有序数组的平方 、209.长度最小的子数组、 59.螺旋矩阵II

代码随想录

[注：题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum]

目录

977.有序数组的平方

209. 长度最小的子数组

59. 螺旋矩阵 II

今天还是给老板弄了一天申请书，麻了。时间紧，任务重，就浅二刷了一下977和209，59明早补上。

977.有序数组的平方

给你一个按?非递减顺序?排序的整数数组?nums，返回?每个数字的平方?组成的新数组，要求也按?非递减顺序?排序。

输入：nums = [-4,-1,0,3,10]

分析可知，数组元素平方后是由外到内递减的，故可以考虑从数组两端向中间遍历，即使用双指针分别指向首尾。

/**
     * 977. 有序数组的平方
     * @param nums  非递减顺序 排序的整数数组
     * @return 返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序
     */
    public static int[] sortedSquares(int[] nums) {
        //输入：nums = [-4,-1,0,3,10]  输出：[0,1,9,16,100]
        int[] array = 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]){
                array[index] = nums[right] * nums[right];
                right--;
            }else {
                array[index] = nums[left] * nums[left];
                left++;
            }
            index--;
        }
        return array;

209. 长度最小的子数组

给定一个含有?n?个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组?[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

一刷是直接两个for暴力解决，二刷时考虑使用一个for解决战斗，即滑动窗口（核心还是双指针）。这里一个指针用来遍历整个数组（即用来确定终点），另一个指针用于滑动窗口，即当窗口值大于s后减去最左边的值，使窗口右移。

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

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。这里就是用来比较每次窗口值大于s后的子数组长度。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

/**
     * 209. 长度最小的子数组
     * @param target 正整数
     * @param nums n 个正整数的数组
     * @return 返回该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] 的长度。
     */
    public static int minSubArrayLen(int target, int[] nums) {
        //输入：target = 7, nums = [2,3,1,2,4,3]    输出：2
        int sum = 0;
        int len = nums.length + 1;
        int temp;
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // 这里就是滑动窗口的核心
            while (sum >= target){
                temp = i - j + 1;
                len = Math.min(len, temp);
                sum -= nums[j];
                j++;
            }
        }
        if (len == nums.length + 1){
            return 0;
        }
        return len;

补上59. 螺旋矩阵 II

59. 螺旋矩阵 II

给你一个正整数?n?，生成一个包含?1?到?n2?所有元素，且元素按顺时针顺序螺旋排列的?n x n?正方形矩阵?matrix?。

输入：n = 3  输出：[[1,2,3],[8,9,4],[7,6,5]]

这道题的核心是遍历矩阵，可坐标系来描述矩阵元素的位置，即使用双指针，一个指针i表示x轴（行），一个指针j表示y轴（列）。同时对于矩阵每条边上元素的赋值需要一个统一的规则，即循环不变量（即区间，这里使用左闭右闭区间）。

下次更上n*m矩阵。

?

/**
     * 59. 螺旋矩阵 II
     * @param n 一个正整数 n
     * @return 返回一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix
     */
    public static int[][] generateMatrix(int n) {
        // 输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
        // 双指针+循环不变量
        int i ;// 行
        int j ;// 列
        int loop = 0;
        int start = 0;
        int count = 1;
        int[][] matrix = new int[n][n];
        while (loop++ < n / 2){
            // 上侧从左到右
         //这里的区间取的是[start, i]，每条边的循环不变量都是2，对于第一层循环即是[0, 2]
            for (i = start; i < n - loop; i++) {
                matrix[start][i] = count++;
            }
            // 右侧从上到下
            for (j = start; j < n - loop; j++) {
                matrix[j][i] = count++;
            }
            // 下侧从右到左
            for (; i >= loop; i--) {
                matrix[j][i] = count++;
            }
            //左侧从下到上
            for (; j >= loop; j--) {
                matrix[j][i] = count++;
            }
            start++;
        }
        if (n % 2 == 1){
            matrix[start][start] = count;
        }
        return matrix;