代码随想录刷题笔记（DAY2）

今日总结：今天在学 vue 做项目，学校还有很多作业要完成，熬到现在写完了三道题，有点太晚了，最后一道题的题解明天早起补上。

Day 2

01. 有序数组的平方（No. 977）

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

1.1 笔记

这道题我一开始是准备使用比较器根据绝对值排序来实现的，但是 Comparator<Integer> 是无法作用于 int[] 的，小小踩坑

然后回想起昨天的双指针思想，这道题可以通过两个分别指向负数和正数的，因为是非递减排序的，所以负数是按照绝对值非递增排序的，也就是前一个负数的绝对值一定大于后一个负数的绝对值，平方也同理。

所以不妨设置一个新数组来存储这些元素，利用 left 指针去遍历小于零的元素，right 指针去遍历大于零的元素，当遍历结束后（如果有）剩余的元素，也就是正数和负数个数不相等的情况，就按照绝对值的顺序继续放入新数组。

1.2 代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] resArr = new int[nums.length]; // 存储结果的新数组
        int index = resArr.length - 1; // 从后往前循环赋值新数组
        // 正数组直接返回结果
        if (nums[left] >= 0) {
            for (int i = 0; i < nums.length; i++) {
                nums[i] = nums[i] * nums[i];
            }
            return nums;
        }
        // left 索引负数部分，right 索引整数部分
        while (nums[left] < 0 && nums[right] >= 0) {
            if (Math.abs(nums[left]) > nums[right]) {
                resArr[index] = nums[left] * nums[left];
                index--;
                left++;
            } else if (Math.abs(nums[left]) < nums[right]) {
                resArr[index] = nums[right] * nums[right];
                index--;
                right--;
            } else {
                // 相等的情况，赋值两次
                resArr[index] = nums[left] * nums[left];
                index--;
                resArr[index] = nums[left] * nums[left];
                index--;
                left++;
                right--;
            }
        }
        if (nums[left] >= 0) {
            // 负数部分已经遍历完，处理正数部分
            for (int i = index; i >= 0; i--) {
                resArr[i] = nums[right] * nums[right];
                right--;
            }
        } else if (nums[right] < 0) {
            // 说明正数部分已经遍历完了
            for (int i = index; i >= 0; i--) {
                resArr[i] = nums[left] * nums[left];
                left++;
            }
        }
        return resArr;
    }
}

02. 长度最小的子数组（No. 209）

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

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

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

2.1 笔记

这道题采用的是滚动数组的方法，所谓滚动数组就是不断的调节子序列的起始和终止的位置，从而得出我们想要的结果，首先要考虑的是我们遍历的是数组的起始位置还是终止位置，如果遍历的是起始位置的话那终止位置该如何确定？通过 for 循环继续向后遍历，来确定以每个元素为起始元素所得到的所有的子数组，这样就是暴力解法，显然时间复杂度是不符合题目要求的。

所以我们采用 for 循环遍历终止位置，那要考虑的就是，我们的起始位置该什么时候更新呢？很明显，当我们循环遍历直到这个数组的 sum 和大于等于题目中的 target 起始位置向后移动缩小范围，这样就避免了暴力解法中我们每到一个起始位置都要从头开始加和：通过起始位置的向后递增，这时候我们的 sum 应该等于原本的 sum 减去每次的 nums[i] **直到 **我们发现 sum < target 就再去更新终止位置的值，这样就实现了数组滚动前进的效果，遍历以 nums 中的每个元素作为结尾的所有子数组。

2.2 代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0; // 起点
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        for (int j = 0; j < nums.length; j++) {
            // 外层去循环遍历滑动窗口的终点，起点在找到符合的区间再更新
            sum += nums[j];
            // 一直使起始位置向后移动直到 sum < target 为止
            while (sum >= target) {
                // 更新最短的值
                minLen = Math.min(minLen, (j - i + 1));
                // 移动起始位置
                sum -= nums[i];
                i++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

03. 螺旋矩阵 II（No. 59）

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

示例 1：

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

示例 2：

输入：n = 1
输出：[[1]]

3.1 笔记

3.2 代码

class Solution {
    public int[][] generateMatrix(int n) {
        int index = 0;
        int loop = 0; // 控制循环次数，总共需要遍历 n / 2 次
        // n 阶矩阵
        int[][] res = new int[n][n];
        int start = 0;
        int i, j; // 因为遍历另一条边的时候需要前一条边的结束位置，需要保存
        int count = 1; // 这是每次填充的数字
        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;
    }
}